[BOJ] 잃어버린 괄호(1541) 문제 풀이 | Python3

---

이 문제는 그리디 구현 알고리즘이다. 괄호를 적절히 쳐서 최소값을 만들어 내는 문제이다.

50+40+70-30-5+10 식을 보자 -(5)+(10)=5 보다는 -(5+10)=-15 가 최소임을 알 수 있다.

- 부호가 나올 때 까지 숫자와 + 는 괄호 안에 넣어주면 최소값을 구할 수 있다.

(50+40+70) - (30) - (5+10) 이렇게 말이다. 

exp=input()
stack=[] # 괄호 안 숫자 저장용
n='' # 숫자 저장용
result=0 # 최종 결과
mode=1 # 연산 부호 
 
for e in exp:
    if e.isdigit(): n+=e  # 숫자이면 n에 더한다. ex) n+='5'
    else:
        if e=='+': # + 이면 n을 숫자로 변환해 괄호 안 숫자 리스트에 넣는다
            stack.append(int(n))
        elif e=='-': # - 이면 괄호 안에 있는 숫자들과 숫자로 변환한 n을 모두 더한 후 # mode 부호에 맞게 result 에 더해준다.
            result+=(int(n)+sum(stack))*mode
            mode=-1; stack=[] # 다음 괄호에 대해 - 해줘야하므로 mode=-1 변경 후 괄호 초기화
        n='' # 부호 전에 나온 숫자를 처리해줬으므로 다음 숫자를 위해 n 초기화
 
result+=(int(n)+sum(stack))*mode # 마지막 괄호에 대해 
print(result)