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

문제. 백준 1541번 잃어버린 괄호

---

문제 설명

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

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

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

입력

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

출력

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

 

출처 : 백준 1541번 잃어버린 괄호

1541번: 잃어버린 괄호

---

나의 풀이 in Python3

#1 (런타임 에러 - 실패)

import re
expression = re.split('-',input())
answer = [str(eval(i)) for i in expression]
print(eval('-'.join(answer)))

문제는 간단했습니다.

 

최소로 만들기 위해서는 -가 나올 때마다 split해주고 +가 있는 부분은 합을 해줍니다. 마지막으로 -로 split한 리스트를 합쳐서 -해주면 최솟값이 나옵니다.

그래서 저는 string으로 이루어진 수식을 int처럼 수식해주는 eval() 함수를 사용해보았는데 런타임 에러가 계속 떠서 실패하였습니다. 너무 궁금해서 이유를 찾던 중 문제의 입력사항에 숫자 값이 0으로 시작할 수도 있다는 것을 보고 input에 '07-40+40' 이런 식으로 예제를 만들어서 넣어봤습니다. 'invalid token'이라는 경고와 함께 런타임 에러가 뜨는 것을 보고 eval() 함수는 0으로 시작하는 값을 인식을 못한다는 사실을 알아냈고 다른 방식으로 풀어보았습니다.

 

#2 (성공)

#[BOJ] 1541. 잃어버린 괄호
import re
expression = re.split('-',input())
the_plus = []
for i in expression:
    if '+' in i:
        plus = list(map(int,i.split('+')))
        the_plus.append(sum(plus))
    else:
        the_plus.append(int(i))
answer = the_plus[0]
for i in the_plus[1:]:
    answer -= i
print(answer)

제가 할 수 있는 선에서 최대한 간결하게 만들어보았습니다.

먼저, the_plus라는 리스트에 '+' 수식이 있을 경우 해당 값을 계산해주고 없을 경우 int로 만들어주어 넣어줬습니다.

그리고 -로 input을 했기에 첫 번째 순서부터 차례대로 -해줌으로써 값을 만들었습니다.

int()를 해줄 경우, 0으로 값이 시작하여도 자동으로 0이 제거된 int값이 나오므로 앞서 에러난 부분이 고쳐짐을 알 수 있었습니다.

간단하고 편리한 함수라도 치명적인 에러가 나올 수 있기에 조심해서 써야 한다는 점을 배울 수 있었습니다.

 

알고리즘 풀이

1. 최소값을 얻기 위해서는 - 수식 바로 앞에서 다른 -가 나올 때까지 괄호화 : '-' split
2. 괄호 안 '+' 수식을 위해 the_plus 리스트에 '+' 수식 적용된 값 합산
3. answer에 괄호 안 '+'수식이 완성된 값을 순서대로 '-' 수식 적용하여 최소값 산출