리트코드 - 150. Evaluate Reverse Polish Notation

리트코드 - 150. Evaluate Reverse Polish Notation

출처 - https://leetcode.com/problems/evaluate-reverse-polish-notation/?envType=study-plan-v2&envId=top-interview-150

 

문제 설명

주어진 문자열 배열 tokens은 역폴란드 표기법(Reverse Polish Notation)으로 표현된 산술 식을 나타냅니다.

이 식을 계산하여 결과값을 반환하세요. 반환값은 식의 값을 나타내는 정수입니다.

 

주의 사항:

• 유효한 연산자는 '+', '-', '*', '/'입니다.
• 각 피연산자는 정수나 다른 식일 수 있습니다.
• 두 정수 사이의 나눗셈은 항상 0으로 내림합니다.
• 0으로 나누는 나눗셈은 발생하지 않습니다.
• 입력은 역폴란드 표기법으로 유효한 산술 식을 나타냅니다.
• 답변 및 중간 계산 결과는 32비트 정수로 표현할 수 있습니다.

 

의사코드

스택 생성 반복문 시작 (tokens 배열 1칸식 순회)     if 연산자이면         연산자 = 배열값;         num1 = 스택 값 꺼냄         num2 = 스택 값 꺼냄         스택에 num2에서 num1을 연산한 값 저장     else         배열값을 스택에 저장 반복문 종료 스택에 남은 값 꺼냄 함수 isOperator(토큰 값)     +,-,*,/ 일때만 true 리턴 함수 calculator(num1, num2, 연산자)     num2 에서 num1 연산 리턴

 

풀이코드

class Solution {
    public int evalRPN(String[] tokens) {
        Stack<Integer> numStack = new Stack<>();

        for (int i = 0; i < tokens.length ; i++) {
            if (isOperator(tokens[i])) {
                String operator = tokens[i];
                int num1 = numStack.pop();
                int num2 = numStack.pop();
                numStack.push(calculate(num1, num2, operator));
            } else {
                int num = Integer.parseInt(tokens[i]);
                numStack.push(num);
            }
        }

        return numStack.pop();

    }

    public boolean isOperator(String token) {
        return token.equals("+") || token.equals("-") || token.equals("*") || token.equals("/");
    }

    public int calculate(int num1, int num2, String operator) {
        if (operator.equals("+")) {
            return num2 + num1;
        } else if (operator.equals("-")) {
            return num2 - num1;
        } else if (operator.equals("*")) {
            return num2 * num1;
        } else {
            return num2 / num1;
        }
    }

}

코드설명

stack을 활용하는 문제로 숫자를 저장하는 numStack을 만든다.

그리고 tokens 배열을 순회하며 숫자가 있는 경우 계속 numStack에 저장하다가 연산자를 만나면 연산을 시작한다.

 

예를 들어 tokens = {"2","3","/"} 인 경우 2 / 3 연산을 해 주어야 하는데,

중요한 것은 스택은 제일 마지막에 저장한 값이 꺼낼 때 튀어(pop) 나오므로 처음 pop() 값을 두번째 인자로, 그다음 pop() 한 값을 첫번째 인자로 연산해줘야 한다.

 

이렇게 연산된 값을 다시 numStack에 넣어주고 반복문을 돌리면 numStack에는 값이 한 개만 남게되는데, 이 값을 pop 하면 원하는 결과를 얻을 수 있다.

 

시간복잡도 - O(n) (tokens배열을 순회하는데 걸리는 시간)

공간복잡도 - O(1)

 

문제를 풀며 생각한 흐름과 배운 점

잘못된 생각

처음에는 stack을 두개 만들어서 하나는 numStack에 숫자를 넣고, 하나는 operatorStack에 넣는 방법을 생각했다.

이렇게 하다보니 연산을 뒤에서부터 하는 문제가 발생했고, stack을 활용할수가 없었다.

 

그래서 이번에는 거꾸로 반복문을 돌려 거꾸로 저장해보기로 했다.

import java.util.Stack;

class Solution {
    public int evalRPN(String[] tokens) {
        Stack<Integer> numStack = new Stack<>();
        Stack<String> operatorStack = new Stack<>();

        for (int i = tokens.length - 1; i >= 0; i--) {
            if (isOperator(tokens[i])) {
                operatorStack.push(tokens[i]);
            } else {
                int num = Integer.parseInt(tokens[i]);
                numStack.push(num);
            }
        }
        int result = 0;
        while (!operatorStack.isEmpty()) {
            String operator = operatorStack.pop();
            int num1 = numStack.pop();
            int num2 = numStack.pop();
            result = calculate(num1, num2, operator);
            numStack.push(calculate(num1, num2, operator));
        }

        return result;

    }

    public boolean isOperator(String token) {
        return token.equals("+") || token.equals("-") || token.equals("*") || token.equals("/");
    }

    public int calculate(int num1, int num2, String operator) {
        if (operator.equals("+")) {
            return num1 + num2;
        } else if (operator.equals("-")) {
            return num1 - num2;
        } else if (operator.equals("*")) {
            return num1 * num2;
        } else {
            return num1 / num2;
        }
    }

}

하지만 이 방법도 문제가 발생했다.

연산자는 앞에서부터 꺼내는게 맞는데, 숫자도 앞에서부터 꺼내게 되어버렸으니 말이다.

 

그래서 문제를 다시보고 흐름도를 적어봤다.

 

1. 숫자가 저장되다가 연산자를 만나면 바로 앞에 두 숫자만 연산한다.

2. 연산자를 만나면 그 즉시 연산하면 된다.

 

이렇게 생각이 정리되니 operatorStack은 필요없는 게 되었다.

숫자만 계속 저장하다가 연산자 만나면 앞에 두개를 연산하면 되는거였다.

이렇게 생각하니 제대로 된 코드를 짤 수 있었다.

 

다른코드

class Solution {
    public int evalRPN(String[] tokens) {
        Stack<Integer> stack = new Stack<>();
        Set<String> ops = Set.of("+", "-", "*", "/");

        for (String s : tokens) {
            if (ops.contains(s)) {
                int a = stack.pop();
                int b = stack.pop();
                int c = 0;
                
                switch(s) {
                    case "+":
                        c = b + a;
                        break;
                    case "-":
                        c = b - a;
                        break;
                    case "*":
                        c = b * a;
                        break;
                    case "/":
                        c = b / a;
                        break;
                }
                
                stack.push(c);
            }
            
            else stack.push(Integer.parseInt(s));
        }

        return stack.peek();
    }
}

set을 이용해서 연산자를 정리해주었더니 코드가 더 깔끔해졌다.

 

나도 처음에는 저 연산자를 enum처리하면 어떨까하고 생각했는데 객체를 따로 만들어서 처리하는게 가독성을 떨어뜨렸었다.

연산자는 중복되지 않으니 set을 사용하는 것이 맞는 것 같다.

 

정리

stack을 사용하기 전에는 어디에 어떻게 쓸지 고민하고 사용하기