백준 1541번 python 풀이 - 잃어버린 괄호

문제 링크

1541번

해결책

import sys

num_list = []
oper_list = []

raw_str = sys.stdin.readline().rstrip()
i = 0
temp = 0
while (i <= len(raw_str) - 1):
    if raw_str[i] == "+" or raw_str[i] == "-":
        num_list.append(temp)
        oper_list.append(raw_str[i])
        temp = 0
    else:
        temp *= 10
        temp += int(raw_str[i])
    i += 1

num_list.append(temp)

# 만약 - 가 들어오면, 그 뒤의 것들을 괄호로 묶는다?
# 근데 10 - 9 - 1100 이면 괄호로 안묶는게 더 좋지 않나?
# 그러면, - 뒤에 + 가 올때 괄호를 묶는다?
# 10 - 9 + 1 - 1000
# 10 - 9 - 1000 + 1
# 오 이거 맞는것 같다.

_sum = 0

ans = ""

num_ptr = 0

open_cnt = 0
ans += str(num_list[num_ptr])
for oper_idx in range(len(oper_list)):
    oper = oper_list[oper_idx]

    if oper == "-":

        for i in range(open_cnt):
            ans += ")"
        open_cnt = 0

        ans += "-"

        if(oper_idx!=len(oper_list)-1):
            if oper_list[oper_idx + 1] == "+":
                ans += "("
                open_cnt += 1
        num_ptr += 1
        ans += str(num_list[num_ptr])
    elif oper == "+":
        ans += "+"
        num_ptr += 1
        ans += str(num_list[num_ptr])



if open_cnt != 0:
    for i in range(open_cnt):
        ans += ")"


print(eval(ans))

주석으로 달 설명

그리디, 쉬운 문제…? 이번 문제는 결국 괄호의 배치의 규칙을 찾는 것에 있던 것 같다. 결괏값을 모두 비교하는 것보다는 빠르니… 일단 + 이 들어오는 경우는 무시하고, 만약 - 가 들어온다면, 먼저 이전에 열은 괄호를 모두 닫아버린다. 그래야 뒤의 값도 빼줄수 있으니까. 그리고, - 뒤에 덧셈이 들어온다면, 괄호를 열어버린다. 이런 방식으로 진행했더니 완료되었다.