[백준] 1541번 잃어버린 괄호 Python 풀이

문제 ✏️

---

세준이는 양수와 +, -, 그리고 괄호를 가지고 식을 만들었다. 그리고 나서 세준이는 괄호를 모두 지웠다.

그리고 나서 세준이는 괄호를 적절히 쳐서 이 식의 값을 최소로 만들려고 한다.

괄호를 적절히 쳐서 이 식의 값을 최소로 만드는 프로그램을 작성하시오.

입력

---

첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’ 만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 많이 연속되는 숫자는 없다. 수는 0으로 시작할 수 있다. 입력으로 주어지는 식의 길이는 50보다 작거나 같다.

---

입력 & 출력 예시

input

55-50+40

output

-35

풀이

---

괄호를 적절한 곳에 쳐서 식의 값을 최소로 만드는 전형적인 그리디 알고리즘 문제이다.

우선 숫자들과 기호들을 분리하여 따로 리스트에 저장한 후,
스택 형태의 숫자, 연산기호 리스트를 하나씩 pop() 하면서 , + 기호가 나타나면 숫자들을 더해주고 , - 기호가 나오면 -1 을 더해온 값에 곱해주고 더했다.

예를 들어 , 식이 55-50+40 라면

각각 num , s 스택에

num	연산기호
40
50	+
55	-

다음과 같이 저장될 것이고 각 리스트의 원소를 pop() 해줘서 연산식을 구성하면 식의 연산순서를 저해하지 않고, 최소값을 만들 수 있을 것이다.

(40+50)*(-1) +55

이렇게 될 것 이다.

N = input() 
s=[] # 연산기호가 들어가는 리스트
num=[] # 숫자들이 저장되는 리스트
sub='' 
pre=0 
answer=0

# 숫자와 연산기호들을 분리
for x in N:
    # print(x)
    if x =="+" or x =="-": 
        s.append(x)
        num.append(sub) 
        sub=''
        continue
    sub += x # '+','-' 가 아니면 sub에 저장해놓음
num.append(sub) # 마지막으로 남는 숫자 append

# 리스트 안에서 루프 돌리기 위해
num.reverse() 
s.reverse()

# 두 리스트의 원소 갯수가 다르면
if(len(num)!=len(s)): 
    answer+=int(num.pop()) 
for x in range(len(num)):
    if(s[x]=='+'):
        pre+=int(num[x])
    else:
        pre+=int(num[x])
        answer+=(-1)*pre
        pre=0
if(pre!=0):
    answer+=pre

print(answer)