삼성 1224. 계산기3

문제 링크

난이도	정답률(_%)
D4	90.93%

설계

고생한 점

• 역시 시간복잡도 계산하기 어렵다 🙄

복잡도 계산

문자열 길이를 n이라고 함. 최대 길이가 안주어져있음..

시간복잡도

• 후위 연산으로 변환 할 때 n번 회전하면서, 연산자일 경우 최대 Stack 길이만큼 연산자를 비교하는 과정이 a번 들어갈 수 있음 (a < n)
• 후위 연산식을 계산하는 과정 n번
• 더하면! O(n)?

공간복잡도

• 입력받은 연산식 char형 길이 n
• 후위 연산식 char형 길이 n
• 후위 연산자가 쌓이는 Stack
• 후위 연산식 계산에서 피연산자가 쌓이는 Stack

풀이

• 중위 연산식 문자열을 후위연산식으로 변환한다.
• 변환한 후위연산식을 계산. 아래 과정을 연산식을 다 돌 때까지 반복한다.
  • 피연산자일 경우 피연산자 Stack에 저장한다.
  • 연산자일 경우 피연산자 Stack에서 값을 2개 꺼내서 계산한 뒤, 결과값을 피연산자 Stack에 추가한다.
• 모든 연산식을 돌면 피연산자 Stack에서 값(=결과값)을 꺼내 출력한다.

변환 과정 (모든 문자열을 돌 때까지 1-3 반복)

1. 피연산자일 경우 연산식에 추가
2. 스택이 비었거나 (일 경우 연산자 Stack에 추가
3. 연산자일 경우
   • )가 아닌 연산자의 경우 연산자 Stack의 값과 연산자의 우선순위를 비교한다.
     • 우선순위가 높은 경우, Stack에 연산자를 넣음.
     • 우선순위가 낮거나 같은 경우, 현재 연산자의 우선순위가 높을 때까지 연산자 Stack에서 값을 pop하여 후위 연산식에 추가하고, 연산자 Stack에 현재 연산자를 넣는다.
   • 연산자가 )인 경우
     • 연산자 Stack에서 ( 를 만날 때까지 값을 pop하여 후위 연산식에 추가한다.
4. 모든 연산식을 다 돌았으면 Stack에 남은 연산자들을 후위 연산식에 추가한다.

코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Stack;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int testCase = 10;

        for (int i = 0; i < testCase; i++) {
            br.readLine(); // 문자열 길이 입력 날림
            char[] infixOperations = br.readLine().toCharArray();
            char[] postfixOperations = makePosfix(infixOperations);
            Stack<Integer> operands = new Stack<>();

            for (char operation : postfixOperations) {
                if (operation >= '0' && operation <= '9') {
                    operands.push(operation - '0');
                    continue;
                }

                int number2 = operands.pop();
                int number1 = operands.pop();

                operands.push(calculate(number1, number2, operation));
            }

            StringBuilder sb = new StringBuilder();
            sb.append("#");
            sb.append(Integer.toString(i + 1));
            sb.append(" ");
            sb.append(Integer.toString(operands.pop()));
            sb.append("\n");

            bw.write(sb.toString());
        }

        bw.flush();
        bw.close();
    }

    public static int calculate(int number1, int number2, char operator) {
        if (operator == '*') {
            return number1 * number2;
        }

        return number1 + number2;
    }

    public static char[] makePosfix(char[] infixOperations) {
        StringBuilder postfixOperations = new StringBuilder();
        Stack<Character> operators = new Stack<>();

        for (char operation : infixOperations) {
            if (operation >= '0' && operation <= '9') {
                postfixOperations.append(operation);
                continue;
            }

            if (operators.isEmpty() || operation == '(') {
                operators.push(operation);
                continue;
            }

            while (!operators.isEmpty()) {
                if (operation != ')') {
                    int priorityGap = getPriority(operators.peek()) - getPriority(operation);

                    if (priorityGap < 0) {
                        break;
                    }
                }

                char operator = operators.pop();

                if (operator == '(') {
                    break;
                }

                postfixOperations.append(operator);
            }

            if (operation == ')') {
                continue;
            }

            operators.push(operation);
        }

        while (!operators.isEmpty()) {
            postfixOperations.append(operators.pop());
        }

        return postfixOperations.toString().toCharArray();
    }

    public static int getPriority(char operator) {
        int priority = 0;

        if (operator == '*' || operator == '/') {
            return 1;
        }

        if (operator == '(') {
            return -1;
        }

        return priority;
    }
}