My Solution

+와 -로만 이루어진 식의 적절한 위치에 괄호를 쳐서 결과값이 최소가 되도록 하는 문제이다.

결과가 최소가 되기 위해서는 모든 덧셈을 괄호로 묶어서 빼면 되기 때문에 아래와 같이 구현했다.

1. 식을 파싱해서 숫자와 바로 앞 연산자를 하나의 튜플로 묶는다
2. 각 튜플을 뒤에서부터 확인하면서 +면 temp에 더하고 -면 결과에서 temp를 뺀다.
3. 마지막으로 맨 앞 숫자를 결과에 더한다.

그런데 식을 파싱할 방법이 마땅히 떠오르지 않아 정규표현식으로 먼저 숫자를 분리하고, 다시 원본 문자열을 숫자로 파싱하여 연산자를 얻어내었다.

line = sys.stdin.readline().strip()

num = re.split('[+-]', line)
operation = []
for s in re.split('[0123456789]', line):
    if s != '':
        operation.append(s)
operation.insert(0, '$')

result = 0
temp = 0

for n, op in reversed(list(zip(map(int,num), operation))):
    temp += n
    if op == '$':
        result += temp
    elif op == '-':
        result -= temp
        temp = 0

print(result)

Better Solution

아무리 생각해도 내 풀이에서 식을 파싱하는게 이상하다고 생각해서 다른 사람의 풀이를 확인 해 보았다.

문제를 잘 생각해보면 두 개의 뺄셈기호 사이에 있는 모든 수들은 더해야하기 때문에 이 풀이에서는 그 점을 이용한다.

먼저 주어진 식을 -로 파싱하면 +로만 이어진 식으로 나뉘게 된다. 이후 각각의 식을 파싱하여 숫자를 더해서 보관하고, 첫번째 숫자에서 각 숫자를 빼주면 답이 나온다.

나는 식에 괄호를 치기 위해 숫자와 연산자를 각각 분리해야 한다는 고정관념에 사로잡혀있었는데, 이 문제에서는 두 연산자를 동시에 처리하지 않아도 되기 때문에 연산자를 하나씩 파싱하면 자연스럽게 괄호를 친 효과를 얻을 수 있다.

line = input().split('-')
num = []
for expr in line:
    temp = 0
    plus = expr.split('+')
    for n in plus:
        temp += int(n)
    num.append(temp)

result = num[0]
for i in range(1, len(num)):
    result -= num[i]
print(result)

-BOJ 1541 잃어버린 괄호