[BOJ/PYTHON] 19591. 독특한 계산기

백준 문제 링크: https://www.acmicpc.net/problem/19591

문제 요약

1. 수식에서 맨 앞의 연산자, 또는 맨 뒤의 연산자 먼저 계산한다. 단, 음수의 부호는 연산자로 취급하지 않는다.
2. 곱셈, 나눗셈을 덧셈, 뺄셈보다 더 먼저 계산한다.
3. 연산자의 우선순위가 같다면 해당 연산자를 계산했을 때 결과가 큰 것부터 계산한다.
4. 계산했을 때 결과 값 또한 같다면 앞에 것을 먼저 계산한다. 

맨 앞 숫자만 음수가 들어올 수 있음

불필요한 0이 앞에 있을 수 있음. (001 + 0002 가능) (출력 시 제거해야)

나눗셈은 나누어지는 수가 양수면 나머지가 0 이상, 음수면 나머지가 0 이하로 처리가 되는 식으로 진행했을 때 나오는 몫을 계산

핵심 아이디어

주의해야 하는 조건만 잘 처리해주면 나머지는 구현이다.

1. 불필요한 0 처리: 입력값을 for문으로 하나하나 돌면서 봤을 때 연산자가 들어오기 전까지는 string에 계속 더해주면 된다. 입력값이 0010+1인 경우 +를 다룰 때 0010을 숫자를 넣는 덱에 int()로 감싸서(숫자로 변환해서) 넣어주면 자연스레 10만 들어간다. 덱을 쓴 이유는 문제에서 맨 앞, 맨 뒤 연산을 먼저 처리하기 때문이다.
2. 맨 첫 음수 처리: 입력값의 0번 인덱스 값이 ‘-’일 경우 첫 번째 수를 음수로 처리해주면 되는 방법이 있다.
   두 번째 방법은 연산자 여부를 확인하는 로직을 손 보면 된다. 입력값을 for문으로 하나하나 돌면서 숫자는 nums 덱에, 연산자는 operators 덱에 넣어줬는데 연산자인지 확인할 때 기존에 숫자를 본 적이 있으면 넣어주면 된다. 즉, string에 이미 넣어둔 숫자들이 있다면 맨 앞 음수 부호가 아니라 연산자라는 것이다. 그러면 맨 앞 음수 부호는 숫자 string에 같이 더해진다. 코드와 함께한 자세한 설명은 아래 트러블슈팅 쪽에 있다.

앞부터 계산해야 하는 경우, 뒤부터 계산해야 하는 경우 분기 처리를 잘 해주고 계산하면 된다. 이때, 계산 로직을 각 분기마다 일일이 적어줬다가 어디서부터 계산해야 하는지 여부를 direction 변수에 넣어두고 실제 계산은 direction 값을 확인하고 방식으로 코드를 정리했다.

direction의 front back은 실수 방지를 위해 상수로 만들어줬다.

풀이

# gold3-19591. 독특한 계산기

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

formula = list(input().rstrip())
nums = deque()
operators = deque()
first_operators = ["*", "/"] # 우선순위 첫 번째
second_operators = ["+", "-"] # 우선순위 두 번째
FRONT, BACK = "front", "back"

def calculator(a, b, operator):
    if operator == "+":
        return a + b
    if operator == "-":
        return a - b
    if operator == "*":
        return a * b
    if operator == "/":
        if a * b >= 0:
            return a // b
        else: return -(-a // b)

num_string = ""        
# nums, operators에 숫자와 연산자 나눠 담기
for x in formula:
    if not x.isnumeric() and num_string: # 숫자가 아니고(연산자이고) 맨 첫 번째가 부호가 아닌 경우 (이미 처리할 숫자가 존재함)
        operators.append(x)
        if num_string: # num_string에 쌓인 값이 있으면 숫자로 변환해서 넣어줌
            nums.append(int(num_string))
        num_string = "" # append 했으니까 비워주기
    else: # 숫자인 경우 혹은 첫 번째 숫자 앞에 부호 붙은 경우
        num_string += x # 0 들어오거나 숫자 두자리수 이상일 경우 커버
if num_string: nums.append(int(num_string)) # 마지막에 남은 애 처리해줌 (연산자가 올 경우에만 숫자를 append해줬기 때문)

while operators:    
    # 맨 뒤 연산자의 우선순위가 더 높을 때 뒤부터
    if operators[-1] in first_operators and operators[0] in second_operators:
        direction = BACK # 처리 방향 뒤부터
    # 맨 앞 연산자의 우선순위가 더 높을 때 앞부터
    if operators[0] in first_operators and operators[-1] in second_operators:
        direction = FRONT
    # 우선순위가 같으면 
    if (operators[0] in first_operators and operators[-1] in first_operators) or (operators[0] in second_operators and operators[-1] in second_operators):
        # 뒤에 거 계산 결과가 더 크면 뒤에 거부터 계산
        if calculator(nums[0], nums[1], operators[0]) < calculator(nums[-2], nums[-1], operators[-1]):        
            direction = BACK
        else: # 결과값이 같거나 앞이 더 크면 앞부터 계산
            direction = FRONT
    
    # 실제 계산 로직
    if direction == FRONT: # 앞부터 계산
        a = nums.popleft()
        b = nums.popleft()
        operator = operators.popleft()
        nums.appendleft(calculator(a, b, operator)) # 계산 결과 넣어주기  
    else: # 뒤부터 계산      
        b = nums.pop()
        a = nums.pop()
        operator = operators.pop()
        nums.append(calculator(a, b, operator)) 

print(*nums, sep='')

Trouble Shooting

시작이 음수인 경우를 한 자리 숫자만 온다고 생각하고 로직 짜서 틀렸었다.

if formula[0] == '-': # 시작이 음수일 때
    nums.append(-int(formula[1]))    
    start_idx = 2
else: start_idx = 0

num_string = ""        
# nums, operators에 숫자와 연산자 나눠 담기
for i in range(start_idx, len(formula)):
    x = formula[i]
    if x.isnumeric():
        num_string += x # 0 들어오거나 숫자 두자리수 이상일 경우 커버
    else: 
        operators.append(x)
        if (num_string != ""): nums.append(int(num_string))
        num_string = ""
if num_string: nums.append(int(num_string)) # 마지막에 남은 애 처리해줌 (연산자가 올 경우에만 숫자를 append해줬기 때문)

그다음 is_first_num_negative 변수를 만들어서 is_first_num_negative이면 음수로 담아주고, 아니면 그냥 처리해주는 로직으로 했다. 이때, nums에 append해주고 is_first_num_negative을 다시 원상태로 안 돌려놔서 그 다음 숫자들도 음수인 거로 취급돼서 원래대로 돌리는 로직을 추가했다.

if formula[0] == '-': # 시작이 음수일 때
    is_first_num_negative = True
    start_idx = 1
else: start_idx = 0

num_string = ""        
# nums, operators에 숫자와 연산자 나눠 담기
for i in range(start_idx, len(formula)):
    x = formula[i]
    if x.isnumeric():
        num_string += x # 0 들어오거나 숫자 두자리수 이상일 경우 커버
    else: 
        operators.append(x)
        if num_string: # num_string에 쌓인 값이 있으면 숫자로 변환해서 넣어줌
            if is_first_num_negative: # 첫 번째 숫자 음수인 경우 음수로 담아줌
                nums.append(-int(num_string))
                is_first_num_negative = False # 처리해줬으니까 원상태로 돌려줌
            else:
                nums.append(int(num_string))
        num_string = "" # append 했으니까 비워주기
if num_string: 
    if is_first_num_negative: # 첫 번째 숫자 음수인 경우 음수로 담아줌
        nums.append(-int(num_string))
        is_first_num_negative = False # 처리해줬으니까 원상태로 돌려줌
    else:
        nums.append(int(num_string)) # 마지막에 남은 애 처리해줌 (연산자가 올 경우에만 숫자를 append해줬기 때문)

코드가 좀 더러워서 정리해줬다. 로직을 좀 바꿨는데, 일단 기존 if문이랑 else문의 위치를 바꿨다. 이렇게 되면 if문에서 연산자 케이스를 커버해주게 된다. if not x.isnumeric()이면 연산자인 경우가 true인데, 이때 and num_string이 있기 때문에 무조건 중간에 낀 연산자만 true이게 된다. 즉, 맨 앞에 - 부호가 오는 경우는 num_string에 += x 된 적 없으니까 num_string이 비어있고, 그래서 else문으로 넘어가게 된다. 맨 첫 음수를 나타내는 - 부호는 else문에 들어왔기 때문에 num_string에 더해지게 되고, 첫 번째 연산자가 나오는 시점에 nums.append(int(num_string))에 의해 음수값으로 nums에 들어가게 된다.

for x in formula:
    if not x.isnumeric() and num_string: # 숫자가 아니고(연산자이고) 맨 첫 번째가 부호가 아닌 경우 (이미 처리할 숫자가 존재함)
        operators.append(x)
        if num_string: # num_string에 쌓인 값이 있으면 숫자로 변환해서 넣어줌
            nums.append(int(num_string))
        num_string = "" # append 했으니까 비워주기
    else: # 숫자인 경우 혹은 첫 번째 숫자 앞에 부호 붙은 경우
        num_string += x # 0 들어오거나 숫자 두자리수 이상일 경우 커버
if num_string: nums.append(int(num_string)) # 마지막에 남은 애 처리해줌 (연산자가 올 경우에만 숫자를 append해줬기 때문)

실행 시간

메모리 47740KB, 시간 888ms (python3)