백준 알고리즘 - 잃어버린 괄호 #1541, Python

백준 링크

첫 번째 시도

먼저 이렇게 시도를 해 보았다.

import sys
p = sys.stdin.readline().strip()
exp = []
# 이전 문자가 기호이면 0, 숫자이면 1
prev = 0
for i in p:
    if i.isdigit():
        if prev == 0:
            exp.append(int(i))
        else:
            exp[-1] = exp[-1]*10+int(i)
        prev = 1
    else:
        exp.append(i)
        prev = 0
m = 0
for i in range(0, len(exp)+1, 2):
    for j in range(i+3, len(exp)+1, 2):
        exp.insert(j, ')')
        exp.insert(i, '(')
        res = eval(''.join(map(str, exp)))
        #print(exp, res)
        if res < m or m == 0:
            m = res
        del exp[i]
        del exp[j]
print(m)

실행을 시키면,

이러한 과정과 함께 얼추 잘 돌아가는 것 같아 보인다!
일단 괄호를 칠 수 있는 곳에 전부 괄호를 넣어서 모든 경우에 대해 계산을 하고, 최솟값을 찾는 방식이다.

문제점

하지만 이런 경우에는? 나의 괄호는 일회용이다...

해결

이 문제에서 기호는 + 또는 - 밖에 존재하지 않는다는 점을 잘 이용해야 한다.
괄호를 통해서, 최초로 -가 온 후의 기호는 전부 마이너스로 생각해도 된다.

import sys
p = sys.stdin.readline().strip()
exp = []
# 이전 문자가 기호이면 0, 숫자이면 1
prev = 0
for i in p:
    if i.isdigit():
        if prev == 0:
            exp.append(int(i))
        else:
            exp[-1] = exp[-1]*10+int(i)
        prev = 1
    else:
        exp.append(i)
        prev = 0
res = 0
# - 기호 이후이면 1, 이전이면 0
mi = 0
for i in exp:
    if i == '-':
        mi = 1
    elif i == '+':
        continue
    else:
        if mi == 0:
            res += i
        else:
            res -= i
print(res)

-가 발견되면 이 앞에 -가 있다고 표시를 해 주고, +는 그냥 무시한다.
그리고, 앞에 -가 있다면 빼기, 없다면 더하기를 하여 답을 완성한다.