[Python] 백준 1541번 잃어버린 괄호(그리디)

문제

풀이

먼저 최소로 바꾸려면 마이너스를 최대로 키워야 한다. 따라서 선형 탐색으로 -를 검출하면 그 뒤에 괄호를 열고 다음 -가 나올 때 괄호를 닫는다. 이렇게 하면 괄호 안에 -가 있을 일은 없고 괄호 맨 앞에 -가 붙기 때문에 음수를 최대한 키울 수 있다.

이 아이디어로 조금 변형한다.

먼저 -를 기준으로 split을 시킨다. 그러면 맨 앞의 list 0번은 무조건 문자열 "?+?...+?"가 된다. 이 문자열은 음수가 될 수 없으니 일단 서로 더해준다.

두 번째부터 마지막 까지 요소들은 모두 -이다. 따라서 +별로 split을 다시 해준 다음 그 숫자들을 모두 더하고 나서 음수로만 바꿔주면 된다.

(요즘 파이썬 list comprehension으로 코드의 양을 줄이는데 맛이 들려 많이 사용하고 있다.)

s = input()

new_s = s.split('-')

if len(new_s) == 1:

    print(sum([int(i) for i in s.split('+')]))

    exit(0)

print(sum([int(i) for i in new_s[0].split('+')])-sum([int(i) for i in ('+'.join(new_s[1:])).split('+')]))