백준 1541번 : 잃어버린 괄호 (Python)

문제 : www.acmicpc.net/problem/1541

1541번: 잃어버린 괄호

 

풀이

숫자와 부호를 나누어 리스트를 만든다. (nums, chars)

주어진 부호는 +와 -밖에 없으므로 모든 +를 먼저 한 뒤에 나온 모든 수에 대해 -를 하면 최소값이 나온다.

a-b+c가 있을 때 a-(b+c) = a-b-c가 되기 때문

chars에서 + 부호의 인덱스가 i라면 nums리스트에서 i와 i+1 인덱스의 값을 더해 nums[i]에 저장한다.

이때 이미 더해진 값임을 표시하기 위해 i+1의 값은 -1로 변경하고, 이후 덧셈을 할 때 -1의 숫자를 가지면 인덱스를 하나씩 앞으로 이동하여 전에 더해진 결과값을 찾아 더한다.

모든 덧셈이 끝난뒤 뺄셈을 진행한다.

 

n = input()
nums = list(map(int, re.split("[+-]", n)))
chars = list(re.findall("[+-]",n))

for i in range(len(chars)):
    if chars[i] == '+':
        k = i
        while nums[k] == -1:
            k -= 1
        nums[k] = nums[k]+nums[i+1]
        nums[i+1] = -1

result = 2*nums[0] 
for i in nums:
    if i != -1:
        result -= i

print(result)