[Python] 백준 15815. 천재 수학자 성필

문제

https://www.acmicpc.net/problem/15815

평행 세계의 성필은 숫자와 연산자를 만든 당대 최고의 수학자이다. 그리고 놀랍게도 이 숫자와 연산자는 현재 우리가 사용하는 것과 같다. 하지만 수식은 연산자가 피연산자 가운데 위치하는 우리와는 다르게 연산자가 피연산자 뒤에 위치한다고 한다.

우리 세계의 식을 성필의 식으로 바꾸는 방법을 간단히 설명하자면 이렇다. 우선 주어진 식을 연산자의 우선순위에 따라 괄호로 묶어준다. 그런 다음에 괄호 안의 연산자를 괄호의 오른쪽으로 옮겨주면 된다.

예를 들어 a+b*c는 (a+(b*c))의 식과 같게 된다. 그다음에 안에 있는 괄호의 연산자 *를 괄호 밖으로 꺼내게 되면 a+bc*가 된다. 마지막으로 또 +를 괄호의 오른쪽으로 고치면 abc*+가 되게 된다.

천재 수학자 성필은 자신이 만든 이런 간단한 식조차 1초 안에 계산하지 못하는 사람들을 위하여 답을 구해주는 프로그램을 개발하려고 했지만 아쉽게도 성필의 세계에는 프로그래밍 언어가 없다. 프로그래밍을 할 수 있는 우리가 성필을 위해 평행세계의 식을 계산하는 프로그램을 만들어주자.

입력

길이가 100이 넘지 않는 수식이 예제 입력과 같이 공백 없이 입력된다. 수식은 0부터 9까지의 숫자와 연산자 '+', '-', '*', '/' 로만 이루어져 있다.

또한, 수식의 계산 중간 과정의 모든 결과는 항상 2,147,483,647을 넘지 않는 정수이고 0으로 나누는 경우는 없습니다.

잘못된 수식이 입력되는 경우도 없습니다.

출력

입력으로 주어진 성필의 수식의 답을 첫째 줄에 출력한다.

---

풀이

이 문제는 후위표기법을 확실하게 이해하면 구현하기 쉬운 문제였다. 

 

예제로 후위표기 계산을 설명하자면...

숫자와 가까운 기호로 계산을 하는 방식이다. 과정을 직접 보여주는 것이 이해하기 쉽기 때문에

 

1) 첫번째 경우(예제) - 123*+

2) 두번째 경우(질문 게시판에서 찾은 반례) - 123*+4+

 

이렇게 가장 왼쪽에 있는 기호와 가장 가까이 있는 두 개의 숫자가 계산된다고 생각하면 될 것 같다!

여기서 집중해야하는 건 '가장 왼쪽에 있는 기호'와 '가장 가까이 있는 두 개의 숫자'인데, 여기서 우리가 떠올려야할 건 바로 스택이다!

 

스택은 후입선출이니, 123을 예시로 보았을때 가장 나중에 들어오는 23을 사용한다고 보면 왜 스택을 사용하는지 알 수 있을 것이다. 숫자가 나오면 스택에 담아주고, 기호가 나오면 바로 스택에 담긴 숫자 두개를 꺼내 계산하고 다시 스택에 넣어주면 된다. 이때, 왜 기호가 나오면 바로! 인 이유는 가장 왼쪽에 있는 기호 그러니까 나온 순서대로 계산을 하면 된다는 뜻이기 때문이다.

 

이 내용을 바탕으로 코드를 작성해보면 다음과 같다!

import sys
input = sys.stdin.readline

susik = input().strip()
giho = ['+','-','*','/']
num = []
for i in susik:
    if i not in giho:
        num.append(int(i))
    else:
        second = num.pop()
        first = num.pop()
        if i == '+':
            num.append(first+second)
        if i == '-':
            num.append(first-second)
        if i == '*':
            num.append(first*second)
        if i == '/':
            num.append(first//second)

print(num.pop())

 

기호 배열을 만들어서 기호인지 아닌지 판별해주고 기호일 경우, 어떤 기호냐에 따라 계산을 해준 다음에 다시 num이라는 스택에 넣어줬다.

 

시간복잡도

음... 길이가 100이 넘지 않는다고 했으니까 O(100)이지 않을까?

사실... 후위표기식은 알고있었는데 조금 돌아가는 바람에 많이 틀렸다 ....ㅎㅎ