[백준 알고리즘][파이썬/Python] 1541번: 잃어버린 괄호

문제

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

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

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

 

입력

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

 

출력

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

 

입출력 예

 

제출 코드

s = input().split('-')

sum = 0
for i in s[0].split('+'):
    sum += int(i)

for i in s[1:]:
    for j in i.split('+'):
        sum -= int(j)

print(sum)

line by line으로 풀이를 하기 전 문제의 핵심을 설명해야 할 것 같다. 먼저, 이 문제는 식의 결과를 최소로 만드는 것이 목적이라는 걸 명심해야 한다. 최초로 마이너스가 나오기 전까지 나오는 숫자는 모두 더할 수 밖에 없으며, 이후 마이너스가 나오는 순간 그 뒤에 있는 모든 수들을 빼주면 된다.

 

입출력 예시의 경우, 50의 왼쪽과 40의 오른쪽에 괄호를 열고 닫았는데, 결국 저 말이 '55 - 50 - 40' 을 만들어버리겠다는 것과 같기 때문이다.

 

(1) line 1

입력받는 값에서 - 기준으로 쪼갠다. 입출력 예는 너무 숫자가 적으니 내가 임의로 만들어봤었다. 만약 입력값이 '50+40+20-60-200-10+30-70' 이라면 s = ['50+40+20', '60', '200', '10+30', '70] 으로 쪼개진다.

 

(2) line 3

모든 숫자의 총합을 담기 위한 변수 sum 선언

 

(3) line 4, 5

리스트 s의 0번째 원소는 맨 처음 숫자부터 연산자 '-'가 나오기 전까지의 숫자들로 구성되어 있으므로, 해당 인덱스에 있는 숫자들은 모두 더해줘야 한다.

 

(4) line 7 ~ 9

리스트 s의 0번째 원소 이후에는 모두 빼줘야 할 숫자들인데, 단독으로 있는 숫자들도 있을 것이고 연산자 '+'와 함께 있는 숫자들도 있을 것이다. 하지만 line 8과 같이 '+'를 기준으로 split해주면 단독으로 있는 숫자들은 그냥 그대로 반환될 것이고, 연산자 '+'와 함께 있는 숫자들은 각각의 숫자로 split될 것이다. 그렇게 split된 숫자들은 모두 빼준다.

 

실패 기록

처음에 나는 정말 이상한 방식으로 접근해서 반은 맞고 반은 틀린 느낌으로 꼬고 꼬아서 생각했다. 입출력 예시를 통해 '-가 나온 다음 +가 나오면 피연산자 두 개는 더해져야 더 큰 숫자를 뺄 수 있겠구나'라고 먼저 생각했고, '그럼 연산자가 +이기 이전에 +일 때, 그 전의 연산자가 -이면 그건 어떻게 체크를 해야 하지?'하며 이상한 생각을 했고 맨 처음엔 스택을 생각했다.

 

근데 5초만에 그건 좀 아닌 것 같다고 생각하고, 입력값을 받으며 split된 덩어리들 안에 '+'가 있는 애들만 따로 리스트를 새로 만들어서 그것들을 어떻게 조리해보려고 생각했다. 심지어 최대 길이가 50이라는 걸 잘못 이해해서 현재 입력값의 길이에서 괄호를 넣을 경우 길이가 2씩 늘어나고, 어쩌면 split된 덩어리들 안에 '+'가 있어도 묶지 못하는 애들도 있겠구나 싶었다. 아, 근데 이게 이렇게까지 가야 하나 싶었고 하다가 뭔가 단단히 잘못되었구나 싶어서 다른 분들의 풀이를 참고했다.

 

평소에도 가벼운 문제를 자꾸 꼬아서 생각하는 경우가 허다한데 어떻게 고칠 수 있을까. 실제 코딩테스트에서도 이러면 진짜 멘탈 바사삭일 것 같다.

 

 

 

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