[백준] 20129 - 뒤집힌 계산기 (G3)

---

문제 소개

---

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

20129번: 뒤집힌 계산기

문제에서 설명하는 계산기를 단순히 구현하는 문제입니다.

차근차근 하나씩 구현하다보면 어렵지 않게 풀 수 있습니다.

---

풀이 과정

---

이 문제가 요구하는 사항은 아래와 같습니다.

 

우선 주어지는 입력이 숫자와 연산자가 뒤섞인 그냥 쌩문자열이기 때문에

0. 문자열을 잘 잘라서 숫자와 연산자를 구분해놔야 합니다.

 

그 다음으로

 

1. 뒤에서부터 앞으로 계산하기

2. 숫자 앞에 의미없는 0을 제거하기

3. 임의로 주어진 연산자 우선순위 순서대로 계산하기

 

이 3가지를 구현하면 됩니다.

---

 

0번 전처리 과정의 경우 정규식을 이용하면

간단하게 숫자와 연산자를 분리해 각각의 리스트를 얻을 수 있습니다.

 

그 다음으로 얻어낸 숫자 리스트에대해 int를 씌워서 앞의 0을 지워냅니다.

그러면 요구사항 2번도 깔끔하게 해결됩니다.

 

이후로는 숫자와 연산자가 뒤섞여있는 리스트가 남아있으니

이 식을 우선순위에 맞게 뒤에서부터 계산만 하면 됩니다.

---

구현방법은 다양하게 있겠지만, 저는 2개의 덱을 사용해 전체 식을 연산자 우선순위에 따라 4번을 훑었습니다.

 

첫번째 덱은 이전 연산의 결과값으로, 이번 연산자 계산에 사용할 덱이고,

두번째 덱은 비어있는 덱으로, 이번 연산자 계산 결과식을 저장할 덱입니다.

 

우선 숫자리스트와 연산자 리스트를 번갈아 순회하면서 첫번째 덱에 주어진 수식을 넣습니다.

 

한번 우선순위가 + > - > / > * 라고 가정해보겠습니다.

 

첫번째 덱을 순회하면서 숫자와 연산자를 만날 때마다 두번째 덱에 집어넣습니다.

이때 연산자를 넣고나서는 마지막으로 어떤 연산자를 넣었는지 변수에 저장해둡니다.

 

숫자를 넣고나서는 해당 숫자가 첫번째 숫자가 아닐 경우, 직전에 반드시 연산자가 있었을 것이므로

그 연산자가 '+' 연산자인지 확인해서 + 연산자라면 두번째 덱에서 + 연산자와 그 이전의 숫자를 빼 연산하고

연산한 결과값을 두번째 덱에 다시 넣습니다.

 

그럼 첫번째 덱의 모든 요소를 꺼내 처리를 마쳤을 때,

두번째 덱에는 모든 + 연산자가 계산이 된 식이 들어있을 겁니다.

 

이제 두번째 덱을 첫번째 덱으로 사용하여 같은 과정을 나머지 연산에 대해서도 반복해주다가

첫번째 덱의 요소가 1개가 되는 순간 반복을 종료하고 해당 요소를 출력하면 됩니다.

---

정답 코드

---

import sys
import re
from collections import deque
input = sys.stdin.readline

seqs = list(map(int, input().split()))
opers = ['+', '-', '*', '/']
oper_seq = sorted(zip(seqs, opers), reverse=True)

exp = input().rstrip()
nums = list(map(int, re.split(r'\*|/|\+|-', exp)))
oper = list(re.sub(r'[0-9]', '', exp))

before = deque()
before.append(nums[0])
for i in range(1, len(nums)):
    before.append(oper[i-1])
    before.append(nums[i])

for i in range(4):
    now_op = oper_seq[i][1]
    d = deque()
    if len(before) > 1:
        n2 = before.pop()
        d.appendleft(n2)
        op = ''
    else:
        break

    while before:
        # n2 가 없다면, before 에서 최근 수를 빼 n2에 넣는다.
        if n2 == '':
            n2 = before.pop()
            # n2 까지 채워진 상황에서, 현재 연산자가 처리해야하는 연산자라면
            if op == now_op:
                # 연산자를 빼고
                d.popleft()

                # n1 에 해당하는 숫자를 뺀다.
                n1 = d.popleft()

                if op == '+':
                    result = n2 + n1
                elif op == '-':
                    result = n1 - n2
                elif op == '*':
                    result = n2 * n1
                elif op == '/':
                    result = n1 // n2
                    if (n1 > 0 and n2 < 0) or (n2 > 0 and n1 < 0):
                        result += 1
                else:
                    raise Exception("not operation")

                # 연산한 결과를 덱에 넣는다.
                d.appendleft(result)
            # 현재 처리하는 연산자가 아니라면 n2를 덱에 넣는다.
            else:
                d.appendleft(n2)

        # n2가 있다면 최근까지 연산을 한 것이므로 연산자를 넣는다.
        else:
            op = before.pop()
            d.appendleft(op)
            n2 = ''

    before = d

print(before.popleft())

지금이 연산자를 넣는 타이밍인지 숫자를 넣는 타이밍인지 확인하기 위해

연산자 뿐만 아니라 숫자도 저장했습니다.

 

원래는 연산자를 넣은 직후에는 최근 넣은 숫자 변수에 -1을 대입하고,

숫자를 넣으면 최근 넣은 숫자변수를 해당 숫자로 바꿔주었었습니다.

그런데 이렇게 작성하니까 중간에 인덱스 오류가 나더라구요.

 

원인을 못찾아서 끙끙 앓았는데, 알고보니 계산 중간에 결과값으로 -1을 덱에 넣고 빼는 경우가 있어서

숫자를 넣고 빼는 상황과 연산자를 넣고 빼는 상황이 겹쳐 생긴 문제였습니다.

 

문제에서 입력으로 주어진 숫자가 모두 양수니까

당연히 -1을 빈 값을 의미하는 용도로 사용해도 될 것이라고 생각한 게 문제습니다.

 

다음에 이런 류의 문제를 푼다면, 입력으로 음이 아닌 정수가 보장되어도

계산 중간에 음의 정수가 나올 수 있다는 점에 유의해야겠네요 ㅋㅋ

 

+

 

위 계산기 문제에서는 나눗셈을 몫연산으로 정의하고 있는데, 그 방식이 C++방식입니다.

파이썬과는 다르기 때문에 음수가 포함된 나눗셈에 대해 추가적인 처리를 해주어야 합니다.