#150 Evaluate Reverse Polish Notation

문제링크 - https://leetcode.com/problems/evaluate-reverse-polish-notation/?envType=study-plan-v2&envId=top-interview-150

문제 조건

• 1 <= tokens.length <= 10^4
• tokens[i]는 "+", "-", "*", "/" 연산자이거나 [-200, 200] 범위의 정수이다.
• 두 정수의 나눗셈은 항상 0으로 나누어진다.
• 0으로 나누는 일은 없다.
• 입력은 후위연산 표현식이다.
• 답과 모든 중간 과정은 32비트 정수로 표현된다.

문제 해결

문제 해결 로직

해당 문제는 후위연산식이 string 배열으로 주어졌을 때 stack을 사용하여 해결할 수 있다.
1. 주어진 string 배열으 데이터를 순차적으로 stack에 숫자들을 저장한다.
2. 연산기호를 만나면 직전에 넣은 두 숫자의 연산을 진행한 후 결과를 stack에 저장한다.
3. 연산이 끝나면 stack에 저장된 연산결과를 반환한다.

데이터 입력

문제에서 입력이 들어오는 데이터는 String s 하나지만 위치 관리를 위해 필요한 변수를 미리 선언해야합니다.

• stack
  배열의 숫자를 저장하고 연산 결과를 저장할 stack.
• a, b
  연산을 진행할 int 임시 저장 변수

      // 기본 stack보다 더 효율적인 ArrayDeque를 사용
      Deque<Integer> stack = new ArrayDeque<>();
      int a;
      int b;

연산하기

후위 연산식이란 연산기호가 앞에 있을 수록 우선 연산을 진행한다.
따라서 입력 받은 배열은 탐색하다가 연산 기호를 만난다면, 해당 연산이 가장 우선 순위라고 판단하여 먼저 연산을 진행하고 해당 연산 결과를 stack에 다시 저장한다.
남은 연산을 동일한 방법으로 진행하면 결과를 얻을 수 있다.

switch(tokens[i]){
            case "+":
              a = stack.pop();
              b = stack.pop();
              stack.push(b+a);
              break;
            case "-":
              a = stack.pop();
              b = stack.pop();
              stack.push(b-a);
              break;
            case "*":
              a = stack.pop();
              b = stack.pop();
              stack.push(b*a);
              break;
            case "/":
              a = stack.pop();
              b = stack.pop();
              stack.push(b/a);
              break;
            default:
              stack.push(Integer.valueOf(tokens[i]));
              break;
          }

코드 작성

class Solution {
    public int evalRPN(String[] tokens) {
      Deque<Integer> stack = new ArrayDeque<>();
      int a;
      int b;

        for(int i=0; i<tokens.length; i++){
          switch(tokens[i]){
            case "+":
              a = stack.pop();
              b = stack.pop();
              stack.push(b+a);
              break;
            case "-":
              a = stack.pop();
              b = stack.pop();
              stack.push(b-a);
              break;
            case "*":
              a = stack.pop();
              b = stack.pop();
              stack.push(b*a);
              break;
            case "/":
              a = stack.pop();
              b = stack.pop();
              stack.push(b/a);
              break;
            default:
              stack.push(Integer.valueOf(tokens[i]));
              break;
          }
        }

        return (int) stack.pop();
    }
}

복잡도 계산

• 시간 복잡도

  • 해당 코드의 시간 복잡도는 입력받은 배열의 크기 n만큼 반복하기 때문에 O(n)의 시간 복잡도를 가진다.
  • case 내부 연산은 O(1)의 시간 복잡도를 가져 총 O(n)의 시간복잡도를 가진다.

• 공간 복잡도

  • 연산을 진행할 숫자를 저장할 stack의 저장 크기만큼 공간 복잡도를 가진다.
  • stack의 저장 크기는 입력 배열 크기 n보다는 작지만 O(n)의 공간 복잡도를 가진다고 할 수 있다.

회고

• 다음과 같은 점수를 기록했다.
  

• 기본 후위 표기식은 stack으로 쉽게 구현할 수 있으며 우선순위를 처리하기 쉽기 때문에 계산기 프로그램을 만드는 과정에서 사용될 수 있다.