[백준] 1541번 - 잃어버린 괄호

https://www.acmicpc.net/problem/1541

 

문제

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

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

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

 

 

 

풀이 (파이썬 사용) - 설명은 아래에 있음.

import re

data = input()
num = []
for cur in re.split('[+|-]', data):
    if not cur:
        continue
    num.append(cur)

count = 0

for i in range(len(data)):
    if data[i] == '+':
        num.insert(count*2+1, '+')
        count+=1
    elif data[i] == '-':
        num.insert(count*2+1, '-')
        count+=1
j = 1
while True:
    if j >= len(num)-1:
        break;
    if num[j] == '+':
        num[j-1] = int(num[j-1]) + int(num[j+1])
        num.pop(j)
        num.pop(j)
        j = j-1
    j = j+1

j = 1
while True:
    if j >= len(num)-1:
        break;
    if num[j] == '-':
        num[j-1] = int(num[j-1]) - int(num[j+1])
        num.pop(j)
        num.pop(j)
        j = j-1
    j = j+1
print(num[0])

 

 

알고리즘 핵심

무조건 더하기(+)를 먼저 한다.

 

 

 

알고리즘 설명

예시 : 55-50+40

 

1) 입력(data)을 -, +을 기준으로 split한다. 이 때, 2개 이상의 문자를 기준으로 split하고 싶으니 re.split을 사용한다. split하여 나온 숫자는 num 배열에 담아준다.

             --> num : [55,  50,  40]

 

2) 입력(data)을 돌면서 +, -를 num 배열에 넣어준다. 이 때, 위치는 count*2+1이다. 이렇게 하면 숫자, 더하기, 빼기가 split 되어 배열에 담기게 된다.

             --> num: [55, -, 50, +, 40]

 

3) 더하기를 모조리 계산한다. 더한 값을 앞의 수에 넣어주고, 부호와 뒤의 수는 pop해준다.

             --> num: [55, -, 90]

 

4) 빼기를 모조리 계산한다. 뺀 값을 앞의 수에 넣어주고, 부호와 뒤의 수는 pop해준다.

             --> num: [-45]

 

5) 답은 num[0]이다.

             --> -45