[백준/Python] 1541번 : 잃어버린 괄호

1541번: 잃어버린 괄호

시간 제한	메모리 제한	문제 티어
2 초	128 MB	실버 II

📜 문제

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

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

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

 

📥입력

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

 

📤출력

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

 

💡풀이

이 문제는 그리디 알고리즘 문제 중 하나이며 막상 풀려고 하면 고민을 조금 해야 하나,풀이 과정을 알게 된다면 은근 쉬웠던 문제였다. 이 문제의 포인트는 바로 '-'를 기준으로 나누는 것이다.

 

먼저 '괄호를 어디다가 두느냐?' => 즉 '어떻게 하면 최솟값을 만들 수 있을까?'의 고민부터 해야 한다. 이에 대한 해결책은 바로 '-' 뒷부분부터 다음 '-'가 나올 때까지 괄호로 묶는 것이다.

 

예를 들어 55-50+40-30+20 에서 괄호를 55-(50+40)-(30+20) 이런 식으로 추가해줘야 저 식의 가장 최솟값인 -85가 나오는 것이다.

 

따라서 split('-')로 -을 기준으로 분리한 List인 formula를 만든 뒤, 거기서 +가 포함되어 있는 식이 인덱스 i 있다면 또 분리시켜 정수화시킨다. 그러고 나서 sum() 함수로 +가 있었던 숫자들의 합계를 구해서 다시 formula[i]에 저장한다.

 

마지막으로 최종 결과를 저장할 변수인 result에다가 맨 처음 formula[0] 을 초깃값으로 해서 저장한 후, 반복문으로 순회하면서 -= 연산자로 빼주기만 하면 끝이다.

 

다음은 내가 작성한 정답 코드이다.

import sys

input = sys.stdin.readline

formula = list(input().rstrip().split('-'))
result = 0

for i in range(len(formula)):
  if '+' in formula[i]:
    formula[i] = sum(list(map(int, formula[i].split('+'))))
  if i == 0:
    result = int(formula[i])
  else:
    result -= int(formula[i])

print(result)