[BOJ] 1541: 잃어버린 괄호

난이도: 실버 2

제한시간	메모리 제한
2 초	128 MB

 

문제

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

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

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

입력

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

출력

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

 

 

---

풀이 기록

1. 문제 파악

문제를 잘 읽어보자.

뺄셈 - 과 덧셈 + 으로만 이루어진 식에서

가장 작은 계산 결과를 얻어야 한다.

 

앞의 숫자가 무엇이 되었든, 뺄셈 뒤의 숫자가 클수록 좋은 것이다.

 

그렇기에, 이 문제의 키는 뺄셈.

 

input을 '-'를 중심으로 split하여 받는다.

fx = input().split(sep='-') # '-' 기준 분리

 

 

 

2. 덧셈 분리

그러면 fx에 저장된 결과가 str 으로 이루어진 list 일 것이다.

이 사이에는 '+' 기호가 숫자와 함께 섞여 있다.

각 요소에 대해서 '+' 를 분리하고, 숫자들을 int로 만든 다음 sum을 해주는 과정이 필요하다.

 

각 항의 int 값을 저장하기 위해 result 배열을 만들어주었다.

result = []

for x in fx:
    num = x.split(sep='+') # 분리된 str 을 다시 '+' 로 분리
    result.append(sum((int(n)*-1 for n in num))) #모든 숫자 음수화 시켜서 sum 후 저장

 

 

 

 

여기에서, 필자는 계산의 용이성을 위해 

모든 항의 부호를 바꿔 주었다. 

 

예시가

55-50+40 이라고 했을 때,

['55', '50+40'] 일 것이고

첫 항은 -55

두번째 항은 -50 과 -40 의 sum 이 result에 저장될 것이다.

 

 

이 때, 항상 식의 맨 처음에는 숫자가 온다고 했기 때문에

result 배열의 첫 요소의 부호만 다시 돌려주면 된다.

 

result[0] *= -1 # 맨 첫 숫자만 원래대로 돌리기
print(sum(result))

 

그 결과의 sum을 출력하면, 문제가 해결된다.