[BOJ]1541. 잃어버린괄호 (python)

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

1541번: 잃어버린 괄호

 

 

문제

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

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

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

입력

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

출력

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

 

풀이

이 문제는 그리디 알고리즘이다.
연산 사이에 괄호를 넣어 최소값을 만들어야 하는데, 결국 -앞에 괄호를 붙이고 새로운 -가 나오면 괄호를 닫고, 다시 괄호를 치는 식으로 하면 최소값을 구할 수 있다.
결국,
문자열을 나열했을 때, 첫번째 마이너스 값이 등장한다면, 그 이후의 모든 숫자들은 전부 빼게 만들 수 있다.
( 5 + 10 - 20 + 10 - 50 + 10 - 20 이라고 하면, - 20 이후는 괄호를 여러번 쳐서 모두 -(20 + 10) - (50 + 10) - (20) 으로 만들 수 있다. 즉, 처음 minus가 등장하고 그 이후의 +는 괄호 안에 포함되어 -가 되고, 이후 등장하는 -도 결국 같은 역할을 하니 -로 작용할 수 있다. 따라서, 첫 - 이후의 모든 연산자는 -라고 생각할 수 있다.)

 

이런 로직을 바탕으로 코드를 짰다!

 

코드

 

 

import sys

formula = list(sys.stdin.readline().strip())

# 숫자들을 str값으로 합쳐서 더해줄 temp 변수
temp = ''
# -가 존재한다면 index를 저장하고, 없다면 최장 길이인 51로 저장
try:
    first_minus = formula.index('-')
except:
    first_minus = 51
ans = 0

# 받은 string이 숫자이면, temp에 더해준다. ('5' '1' 받으면 '51'로 합친다.)
# 받은 string이 연산자이면, 첫번째 - 보다 앞, 뒤에 있는지를 기준으로 ans에 더해주거나 빼준다.
# 이유: - 가 한번이라도 등장하면 그 이후의 숫자들은 모두 빼는 값이 돼야한다. (-가 여러개여도 괄호에 의해 어차피 첫 - 뒤는 전부 음수값으로 변경할 수 있다.)
for i in range(len(formula)):
    s = formula[i]
    if s != '+' and s != '-':
        temp += s
    else:
        if i <= first_minus:
            ans += int(temp)
        else:
            ans -= int(temp)
        temp = ''
if first_minus == 51:
    ans += int(temp)
else:
    ans -= int(temp)
print(ans)