[Python 알고리즘] 1541번 : 잃어버린 괄호

문제

• 세준이는 양수와 +, -, 그리고 괄호를 가지고 식을 만들었다. 그리고 나서 세준이는 괄호를 모두 지웠다. 그리고 나서 세준이는 괄호를 적절히 쳐서 이 식의 값을 최소로 만들려고 한다.
• 괄호를 적절히 쳐서 이 식의 값을 최소로 만드는 프로그램을 작성하시오.

입력

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

# Case 1
55-50+40

# Case 2
10+20+30+40

# Case 3
00009-00009

출력

• 첫째 줄에 정답을 출력한다.

# Case 1
-35

# Case 2
100

# Case 3
0

내가 제출한 풀이 - 정답

1차 (136ms)

import sys
import re

n_str = sys.stdin.readline().strip()
n_list = re.split('[+-]', n_str)

oper_list = list(re.sub('[0-9]', '', n_str))
oper_list.append('+')

temp = 0
res = 0
res_list = []

for i in range(len(n_list)):
    temp += int(n_list[i])

    if oper_list[i] == '-' or i == len(n_list) - 1:
        res_list.append(temp)
        temp = 0

res = res_list[0]

for i in range(1, len(res_list)):
    res -= res_list[i]

print(res)

숫자만 모은 배열과 연산자를 모은 배열을 따로 둬 풀어냈다. 하지만 굳이 정규식을 쓸 필요도 없었으며, 좀 더 코드를 간결하고 보기 좋게 만들고싶었다.

 

2차 (72ms)

import sys

formula = sys.stdin.readline().strip().split('-')

res = 0
res += sum(int(i) for i in formula[0].split('+'))

for i in range(1, len(formula)):
    res -= sum(int(i) for i in formula[i].split('+'))

print(res)

정말 간결해지고 식 또한 복잡하지 않다!! 배열에서 정규식을 사용하지 않아 실행시간 또한 줄었다.

 

문제 해설

이번 문제는 연산식이 문자열로 들어와 괄호를 적절하게 써 최소 값을 구하면 된다.

예를 들어 55-50+40이 들어왔다고 가정하자.

1. 55 - 50 + 40 = 45
2. 55 - (50 + 40) = -35

이렇게 적절하게 괄호를 넣어 구하면 된다.

 

이번 문제는 여러가지의 경우를 다 써보고 규칙을 찾아냈다.

# Case 1
입력 : "100+126-87+47-32"

100 + 126 - 87 + 47 - 32 = 154
100 + (126 - 87) + 47 - 32 = 154
100 + 126 - (87 + 47) - 32 = 60
100 + 126 - 87 + (47 - 32) = 154



# Case 2
입력 : "100+126+87-47+32"

100 + 126 + 87 - 47 + 32 = 298
100 + (126 + 87) - 47 + 32 = 298
100 + 126 + (87 - 47) + 32 = 298
100 + 126 + 87 - (47 + 32) = 234



# Case 3
입력 : "100+126+87+47-32"

100 + 126 + 87 + 47 - 32 = 328
100 + (126 + 87) + 47 - 32 = 328
100 + 126 + (87 + 47) - 32 = 328
100 + 126 + 87 + (47 - 32) = 328

어떠한 규칙이 보이는지 보일 것이다. 바로 -를 제외하고 모든 수를 괄호로 묶어버리면 되는 것이다. 최소를 만들기 위해서는 큰 수를 빼주는 게 무조건 이득이기 때문이다. 이렇게 자신이 하나하나씩 가상의 입력을 내어 찾아보면 하나의 규칙이 보일 것이다.

 

이제는 코드가 어떻게 돌아가는지 직접 확인할 것이다.

모든 입력은 "100+126-87+47-32" 이라고 가정한다.

내 코드는 더러우니 깔금한 코드를 보도록 한다.

formula = sys.stdin.readline().strip().split('-')
# ['100+126', '87+47', '32']

-를 제외하고 모든 수를 괄호로 묶기 위해 -를 제외한 모든 수를 리스트로 바꾸어준다.

 

res += sum(int(i) for i in formula[0].split('+'))
# res = 0 + sum([100, 126])

+ 기호를 기준으로 res에 더해준다.

 

for i in range(1, len(formula)):
    res -= sum(int(i) for i in formula[i].split('+'))
    
"""
    for에서 res의 변화
    res = 226
    res = 92
    res = 60
"""

각각 리스트의 수를 다 더한 다음 res의 값에서 빼준다. 그러면 사실상 (100 + 126) - (87 + 47) - (32)가 된 셈이다.

 

Tip

앞에 0이 들어간 숫자

print(int('00009'))
# 9

python에서는 앞에 0이 있어도 알아서 빼서 변환해준다.