99클럽(2기) - 코테스터디 26일차 TIL # Stack

LeetCode - 682. Baseball Game

You are keeping the scores for a baseball game with strange rules. At the beginning of the game, you start with an empty record.

You are given a list of strings operations, where operations[i] is the ith operation you must apply to the record and is one of the following:

• An integer x.
  • Record a new score of x.
• '+'.
  • Record a new score that is the sum of the previous two scores.
• 'D'.
  • Record a new score that is the double of the previous score.
• 'C'.
  • Invalidate the previous score, removing it from the record.

 

Return the sum of all the scores on the record after applying all the operations.

The test cases are generated such that the answer and all intermediate calculations fit in a 32-bit integer and that all operations are valid.

---

 

1. 첫 번째 풀이

 1) 조건 분석 

 배열로 operations가 들어온다. operations의 요소는 "숫자", "+", "D", "C" 중 하나이다. 요소가 "숫자"일 때는 해당 점수를 기록한다. "+"일 때는 이전 두 점수의 합을 기록한다. "D"일 때는 이전 점수의 두 배를 기록한다. "C"일 때는 이전 점수를 삭제한다. 어떤 요소이든 이전 값에 대한 조작을 해야하므로 자료구조로 스택을 사용하는 것이 편해 보인다.

 

2) 모든 경우의 수에 대한 처리

 for문으로 operations를 순회한다. 이 때 for문은 'for (element: collection) {}' 와 같은 형식으로 사용할 수 있다. for문 안에서 switch문을 사용해서 각 조건에 대한 처리를 해준다. "C"일 때는 이전 점수를 삭제하므로 stack의 pop메소드를 사용한다. "D"일 때는 이전 점수의 두 배를 기록해야 하므로 stack.peek()한 결과의 2배를 push()해준다.

 

 "+"일 때는 이전 두 점수의 합을 기록해야 하므로 일단 현재 맨 위의 값을 pop() 한다. 그래야 그 아래 요소도 접근이 가능하기 때문이다. top을 pop()한 뒤, 그 이전 값을 peek()한 값으로 새로운 top을 만든다. 기존에 pop()한 값을 먼저 push()한 후 새로운 값을 push()하면 이전에 가장 위에 있던 2개의 값을 더한 새로운 top이 제일 위에 위치하게 된다.

 

 "숫자"일 때는 모두 default일 경우로 처리하면 된다. Integer.parseInt(값)으로 해당 값을 Integer로 형변환해준 뒤 stack에 push()한다.

 

3) stack의 모든 요소의 합 반환

  for문으로 stack을 순회하며 모든 요소의 값을 더해서 반환하면 된다.

import java.util.Stack;

class Solution {
    public int calPoints(String[] operations) {
        Stack<Integer> stack = new Stack<>();

        for (String operator: operations) {
            switch (operator) {
                case "C":
                    stack.pop();
                    break;

                case "D":
                    stack.push(2 * stack.peek());
                    break;

                case "+":
                    int top = stack.pop();
                    int newTop = top + stack.peek(); // 원래는 두 번째로 위에 있던 요소를 첫 번째 요소와 더한 값
                    stack.push(top); // 원래 제일 위에 있었던 값을 스택에 먼저 넣음
                    stack.push(newTop); // newTop이 새로운 제일 위의 값이 됨
                    break;
				
                // 숫자 처리
                default:
                    stack.push(Integer.parseInt(operator));
                    break;
            }
        }
        int sum = 0;
        for (int score : stack) {
            sum += score;
        }
        
        return sum;
    }   
}

 

 

2. 느낀점

 최근에 추가된 요소를 참조하거나 제거해야 할 때 스택을 사용하자!