삼성 1223. 계산기2

문제 링크

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

설계

고생한 점

• 역시 시간복잡도 계산하기 어렵다 🙄
• 중간에 테스트한다고 출력했던 문구를 제거 안해서 삼성 사이트에서 Fail 뜸.. 이거 찾느라 고생했다

복잡도 계산

문자열 길이를 n이라고 함.

시간복잡도

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

공간복잡도

• 입력받은 연산식 char형 길이 n
• 후위 연산식 char형 길이 n
• 후위 연산 계산 Stack

풀이

• 중위 연산식 문자열을 후위연산식으로 변환한다. 아래는 변환 방법. 모든 연산식을 돌 때까지 반복한다.
  • 피연산자일 경우 연산식에 추가
  • 연산자일 경우 연산자 Stack의 가장 위 연산자와 우선순위를 비교
    • (현재 연산자가 가장 위 연산자보다) 우선순위가 낮거나 같은 경우
      • 현재 연산자가 높아질 때까지 Stack의 값을 pop하여 연산식에 추가한 뒤 Stack에 현재 연산자를 넣는다.
    • 우선순위가 높은 경우
      • Stack에 값을 넣는다.
• 변환한 연산식대로 후위 연산
  • 피연산자는 스택에 쌓고, 연산자일 경우 2개의 피연산자를 꺼내 계산한 값을 넣으면서 계산하는 방식으로 계산하였다.

코드

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');
                } else {
                    int number2 = operands.pop();
                    int number1 = operands.pop();

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

            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) {
        int result = 0;

        switch (operator) {
            case '*':
                result = number1 * number2;
                break;
            case '+':
                result = number1 + number2;
                break;
        }

        return result;
    }

    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()) {
                operators.push(operation);
                continue;
            }

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

                if(priorityGap < 0){
                    break;
                }

                postfixOperations.append(operators.pop());
            }

            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 == '*') {
            priority = 1;
        }

        return priority;
    }
}