[Grind75-LeetCode] Evaluate Reverse Polish Notation JAVA

반응형

728x90

[Grind75-LeetCode] Evaluate Reverse Polish Notation - Medium 

---

접근

• 스택
• Deque

---

풀이

후위 표기식으로 표현된 식을 계산하는 문제로 연산식은 배열을 통해 주어진다. 스택 자료구조를 공부할 때 후위 표기식을 스택을 통해 계산한다는 내용이 나오기 때문에 쉽게 풀 수 있는 문제이다. 간단하게 후위 표기식에 대해 설명을 하고 넘어가겠다. 

 

후위 표기식이란 쉽게 말해 연산 기호가 숫자 뒤에 나오는 형태를 말한다. 우리가 익숙하게 사용하는 3 + 2 = 5와 같은 형태는 연산자가 가운데 오는 중위 표기식이고 연산자가 앞에 오는 전위 표기식도 존재한다. 이 문제에서 주어지는 후위 표기식의 경우 연산자가 숫자 뒤에 오기 때문에 3 + 2는 32+ 로 표현할 수 있다. 후위 표기법은 연산자가 피연산자 뒤에 위치하기 때문에 괄호가 없어도 연산의 순서를 쉽게 파악할 수 있다. 

 

계산법에 대해선 오히려 더 간단하다고 볼 수 있다. 그냥 순서대로 계산하면 된다. 21+3* 이 식은 예제 1번의 식으로 앞에서부터 숫자가 나오면 스택에 추가하고 연산자가 나오면 스택에 있는 숫자 두 개를 꺼내 계산한 뒤 다시 집어넣으면 끝이다. 

arr = [2, 1, +, 3, *]
Stack = []

arr[0] = 2 -> 스택 추가
Stack = [2]

arr[1] = 1 -> 스택 추가
Stack = [2, 1]

arr[2] = + -> 연산 수행
Stack.pop() = 1
Stack.pop() = 2
+ 연산 수행 = 2 + 1 = 3
Stack.push(3)
Stack = [3]

arr[3] = 3 -> 스택 추가
Stack = [3, 3]

arr[4] = * -> 연산 수행
Stack.pop() = 3
Stack.pop() = 3
* 연산 수행 = 3 * 3 = 9
Stack.push(9)
Stack = [9] 

종료

위의 과정으로 계산이 된다. 코드로 넘어가자.

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

        for (String token : tokens) {
            int num1 = 0;
            int num2 = 0;
            switch (token) {
                case "+":
                    if (stk.size() >= 2) {
                        num2 = stk.pop();
                        num1 = stk.pop();
                        stk.push(num1 + num2);
                    }
                    break;
                case "-":
                    if (stk.size() >= 2) {
                        num2 = stk.pop();
                        num1 = stk.pop();
                        stk.push(num1 - num2);
                    }
                    break;
                case "/":
                    if (stk.size() >= 2) {
                        num2 = stk.pop();
                        num1 = stk.pop();
                        stk.push(num1 / num2);
                    }
                    break;
                case "*":
                    if (stk.size() >= 2) {
                        num2 = stk.pop();
                        num1 = stk.pop();
                        stk.push(num1 * num2);
                    }
                    break;
                default:
                    stk.push(Integer.parseInt(token));
            }
        }

        if (stk.isEmpty()) {
            return -1;
        }
        return stk.pop();
    }
}

제일 처음 작성했던 코드이다. switch 문을 통해 연산자일 경우 연산을 수행하고 연산자가 아닐 경우 스택에 추가해 주었다. 중복되는 코드가 많아 리팩토링을 진행해 주었다.

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

        for (String token : tokens) {
            if (isOperator(token)) {
                int num2 = stk.pop();
                int num1 = stk.pop();
                stk.push(applyOperation(num1, num2, token));
            } else {
                stk.push(Integer.parseInt(token));
            }
        }

        return stk.pop();
    }

연산자인지 체크하는 과정과 연산을 하는 과정을 분리하여 메서드로 뽑아주었다. 정상적인 식인 경우 pop() 과정에서 에러가 발생하지 않기 때문에 체크하는 부분도 없애 버렸다. 물론 정상적인 계산이 가능한 식이 무조건적으로 주어지는 상황이기 때문에 생략한 것이다. 

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

연산자를 체크하는 메서드로 단순히 4개의 연산자 중 하나라면 true를 반환한다.

    private int applyOperation(int num1, int num2, String operator) {
        switch (operator) {
            case "+":
                return num1 + num2;
            case "-":
                return num1 - num2;
            case "*":
                return num1 * num2;
            case "/":
                return num1 / num2;
        }
        return -1;
    }

연산을 수행하는 메서드로 연산이 불가능한 경우 예외를 터트려도 되지만 불가능한 경우가 없기에 -1을 반환해 주었다.

Stack 사용

Stack을 사용하는 방법이 정석이긴 하나 5ms의 실행 시간으로 해결한 코드가 꽤 존재하는 걸로 봐선 성능을 개선하는 방법이 있다는 걸 알 수 있다. 

---

Deque

정답은 Stack 대신 Deque를 사용하는 것이었다. Deque는 Double-ended Queue라는 자료구조로 양방향 큐이다. 양방향구조인 만큼 양쪽 끝에서 요소를 추가하고 제거할 수 있다. 즉 스택과 큐가 합쳐진 형태의 자료구조로 스택을 대신하여 동일하게 사용할 수 있다.

 

자바의 Stack은 Vector 기반의  자료구조이고 Deque는 Queue 기반의 자료구조라는 것에 차이가 있다. 즉 Stack은 배열에 기반한 자료구조이고 Deque는 컬렉션이 기반인 자료구조이다. 배열은 흔히 int [ ] 형태로 사용하는 구조로 초기 생성 시 배열의 크기를 고정적으로 할당하여 생성한다. 그러나 List와 같은 컬렉션 기반의 구조는 요소가 추가되거나 제거될 때 동적으로 크기가 변하는 형태로 이루어져 있다. Stack의 경우 요소를 추가하여 배열이 꽉 찬 경우 크기를 늘린 배열을 다시 생성하여 기존 요소를 복사하기 때문에 재할당에 소요되는 시간이 성능을 저하시키게 되는 것이다. 컬렉션 또한 배열을 사용해 구현되었지만 요소가 추가될 때 배열의 크기를 동적으로 조정하고 재할당을 효율적으로 관리한다. 이 차이로 인해 성능에서의 차이가 발생한다. 

Deque<Integer> stk = new ArrayDeque<>();

코드는 단순히 Stack을 Deque로 선언하는 것 외에는 모두 동일하다. 구현체로 ArrayDeque를 사용한다.

Deque 사용

이렇게 Deque를 사용해 5ms로 1ms 감소시켰지만 0~4ms의 실행 시간을 가지는 코드는 어떤 방법을 사용한 건지 감조차 잡히지 않는다. 

---

전체 코드

class Solution {
    public int evalRPN(String[] tokens) {
        //Stack<Integer> stk = new Stack<>();
        Deque<Integer> stk = new ArrayDeque<>();

        for (String token : tokens) {
            if (isOperator(token)) {
                int num2 = stk.pop();
                int num1 = stk.pop();
                stk.push(applyOperation(num1, num2, token));
            } else {
                stk.push(Integer.parseInt(token));
            }
        }

        return stk.pop();
    }

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

    private int applyOperation(int num1, int num2, String operator) {
        switch (operator) {
            case "+":
                return num1 + num2;
            case "-":
                return num1 - num2;
            case "*":
                return num1 * num2;
            case "/":
                return num1 / num2;
        }
        return -1;
    }
}