[백준] 1541 - 잃어버린 괄호 [Python(파이썬)]

문제

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

1541번: 잃어버린 괄호

 

풀이

언뜻 보면 백트래킹 문제 같은데, 그리디 문제였다. 이 문제의 경우, 만약에 '-'연산자가 하나라도 있으면 뒤에 나오는 피연산자(숫자)들을 모조리 빼주는 것이 최적의 방식이었다. 다음의 예시를 보자.

55-50+40 -> 55-(50+40) = 55-50-40 = -35
55-50+40-20+30 -> 55-(50+40)-(20+30) = 55-55-40-20-30 = -85

이 아이디어만 있다면 나머지는 구현의 문제였다. isdigit( )함수를 사용해서 숫자를 판별하면 파싱을 좀 더 쉽게 구현할 수 있다.

 

코드

import sys

def make_queue():
    temp = ''
    queue = []
    for i, char in enumerate(formula):
        if char == '+' or char == '-':
            queue.extend([temp, char])
            temp = ''
        else:
            temp += char
    queue.append(temp)
    return queue

def cal_queue():
    status = '+'
    result = 0
    for char in queue:
        if status == '-':
            if char.isdigit(): # 숫자이면
                result -= int(char)
        else:
            if char.isdigit():
                result += int(char)
            elif char == '-':
                status = '-'     
    return result

formula = sys.stdin.readline().strip()
queue = make_queue()
print(cal_queue())