[Python] 백준(BOJ): 1541 잃어버린 괄호

문제

1541번: 잃어버린 괄호

---

풀이

수식의 합이 최소가 되도록 계산해야 하는 문자열 greedy 문제이다.

a. 풀이

수식의 합이 최소가 되기 위해서는 - 연산자 뒤의 부분 수식의 값이 최대가 되어야 한다.
따라서 - 연산자를 기준으로 parsing을 수행했다.

• 수식에 + 연산자만 남아있다면 남아있는 수를 모두 더하고 break
• - 연산자가 존재한다면, 해당 index 이후의 부분수식(_data)을 수식(data)에서 제거한 뒤 부분 수식에 대한 합연산을 수행하는 것을 반복

data = input()

answer = 0
# 연산할 값이 남아있을때까지 계산
while data:
    # 수식에 더하기 연산만 있는 경우, 덧셈만 수행하고 바로 return
    if '-' not in data:
        num = [i for i in map(int, data.split('+'))]
        answer += sum(num)
        break

    for x in reversed(range(len(data))):
        if data[x] == '-':
            _data = data[x+1:]
            data = data[:x]
            break
    num = [i for i in map(int, _data.split('+'))]
    answer -= sum(num)

print(answer)