LeetCode : 150. Evaluate Reverse Polish Notation

문제 링크

문제 먼저 읽기

• 문자 배열이 주어집니다.
• 문자는 각각 사칙 연산 1글자씩이거나 숫자인데 Reverse Polish Notation (후위 표기법)산술식을 나타냅니다.
• 연산의 결과를 반환하세요.

Input: tokens = ["10","6","9","3","+","-11","*","/","*","17","+","5","+"]
Output: 22
Explanation: ((10 * (6 / ((9 + 3) * -11))) + 17) + 5
= ((10 * (6 / (12 * -11))) + 17) + 5
= ((10 * (6 / -132)) + 17) + 5
= ((10 * 0) + 17) + 5
= (0 + 17) + 5
= 17 + 5
= 22

• 그 외 조건
  • 1 <= tokens.length <= 10^4
  • tokens[i] is either an operator: "+", "-", "*", or "/", or an integer in the range [-200, 200].

어떻게 풀까?

생각

• 문제 조건에서 int 타입을 사용하면 될 것 같다.
• 얼핏 보면 복잡해 보이지만, 규칙을 따져보면 스택에 숫자를 차곡차곡 넣다가 연산자가 나오면 위에서 2개를 뽑아서 해당 연산자의 값으로 계산하면 되지 않을까?

수도코드

class Solution {
    public int evalRPN(String[] tokens) {
        Stack<Integer> stack = new Stack<>();
        
        for (String s : tokens) { // 연산자가 오면 2개 를 뽑아서 연산한다.
            switch (s){
                case "+": {
                    int a = stack.pop();
                    int b = stack.pop();
                    stack.push(a+b);
										break;
                }
                case "-": {
                    int a = stack.pop();
                    int b = stack.pop();
                    stack.push(a-b);
										break;
                }
                case "*": {
                    int a = stack.pop();
                    int b = stack.pop();
                    stack.push(a*b);
										break;
                }
                case "/":{
                    int a = stack.pop();
                    int b = stack.pop();
                    stack.push(a/b);
										break;
                }
                default: stack.push(Integer.parseInt(s));
            }
        }
        return stack.pop();
    }
}

• 위의 코드는 실패한다. 연산 순서가 중요한 나눗셈과 뺄셈에 주의하자.

class Solution {
    public int evalRPN(String[] tokens) {
        Stack<Integer> stack = new Stack<>();
        
        for (String s : tokens) { // 연산자가 오면 2개 를 뽑아서 연산한다.
            switch (s){
                case "+": {
                    int a = stack.pop();
                    int b = stack.pop();
                    stack.push(b+a);
										break;
                }
                case "-": {
                    int a = stack.pop();
                    int b = stack.pop();
                    stack.push(b-a);
										break;
                }
                case "*": {
                    int a = stack.pop();
                    int b = stack.pop();
                    stack.push(b*a);
										break;
                }
                case "/":{
                    int a = stack.pop();
                    int b = stack.pop();
                    stack.push(b/a);
										break;
                }
                default: stack.push(Integer.parseInt(s));
            }
        }
        return stack.pop();
    }
}

결과

<aside> 💡 Success

Runtime: 5 ms, faster than 98.05% of Java online submissions for Evaluate Reverse Polish Notation.

Memory Usage: 42.7 MB, less than 98.97% of Java online submissions for Evaluate Reverse Polish Notation.

</aside>

다른 풀이 방식과 문제 회고

• 3 ms submission

class Solution {
    public int evalRPN(String[] tokens) {
		 int[] ls = new int[tokens.length/2+1]; // 연산 결과를 저장할 buffer
		    int index = 0;
		    for (String token : tokens) {
		        switch (token) {
		            case "+":
		                ls[index - 2] = ls[index - 2] + ls[index - 1];
		                index--;
		                break;
		            case "-":
		                ls[index - 2] = ls[index - 2] - ls[index - 1];
		                index--;
		                break;
		            case "*":
		                ls[index - 2] = ls[index - 2] * ls[index - 1];
		                index--;
		                break;
		            case "/":
		                ls[index - 2] = ls[index - 2] / ls[index - 1];
		                index--;
		                break;
		            default:
		                ls[index++] = Integer.parseInt(token);
		                break;
		        }
		    }
		    return ls[0];
		}
}

• 따로 스택을 사용하지 않고 연산을 저장할 배열과 커서인 index로 해결한 예시이다.
• Collection을 사용하는 것보다 String[] 을 사용하니 속도가 더 빨라진다.