[Python] 백준 1541 잃어버린 괄호 문제풀이

문제

세준이는 양수와 +, -, 그리고 괄호를 가지고 식을 만들었다. 그리고 나서 세준이는 괄호를 모두 지웠다.

그리고 나서 세준이는 괄호를 적절히 쳐서 이 식의 값을 최소로 만들려고 한다.

괄호를 적절히 쳐서 이 식의 값을 최소로 만드는 프로그램을 작성하시오.

입력

첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 많이 연속되는 숫자는 없다. 수는 0으로 시작할 수 있다. 입력으로 주어지는 식의 길이는 50보다 작거나 같다.

출력

첫째 줄에 정답을 출력한다.

 

문제풀이

 이번 문제는 문자열 파싱을 하는 문제유형이라고 생각한다.

일단, 괄호를 입력하는 것 보다, 가장 작은 결과값을 내기 위한 방법을 이해하면 된다.

우리는 식의 어디에나 괄호를 입력해줄 수 있다. 그리고 식에 괄호를 넣을 때, -를 부호라고 이해하면 쉽게 해결할 수 있다.

 

예를 들어서 1 + 2 - 3 + 4 + 5 - 10 + 9 라는 식이 있다고 가정하면, 가장 작은 식을 입력하기 위해선, 아래와 같이 괄호를 넣어줘야 할 것이다.

1 + 2 - (3 + 4 + 5) - (10 + 9) 

 

위 식을 본다면, 패턴이 보이게 될 텐데, - 연산자가 나오면 다른 - 가 나올 때까지 괄호를 입력해주면 된다.

그렇게 된다면, 그 괄호 내의 모든 수식은 음수로 작용하게 되며, 결과적으로 가장 작은 결과를 출력해낼 수 있다.

 

위 패턴을 이용해서 아래의 순서로 문제를 해결해줄 수 있다.

 

1. 정규표현식을 이용해서 수식에서 숫자와 연산자를 분리해준다.

2. 분리된 수식 전체 구문을 읽어가면서, 결과를 계산한다.

 2-1. 부호가 나오면 현재 부호를 기억해주되, '-'의 부호 계산 중에 발생한 '+' 연산자는 모두 무시한다. (빼기 처리 해주기 위함)

 2-2. 숫자가 나오면, 현재 연산자에 맞게 결과값에 더하거나 빼준다.

3. 결과를 출력한다.

정답코드

import re

total = re.findall(r'[0-9]+|[-+]+', input())

ans = 0
now = ''
for t in total:
    if now == '' and ans == 0:
        ans += int(t)
    elif t in ['+', '-']:
        if not (now == '-' and t == '+'):
            now = t
    else:
        if now == '+':
            ans += int(t)
        else:
            ans -= int(t)
print(ans)