백준 1541 잃어버린 괄호 (파이썬)

실버 2, 그리디, 스택

 

문제: https://www.acmicpc.net/problem/1541

 

문제

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

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

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

입력

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

출력

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

예제 입출력

첫번째 제출 코드 (정답)

import sys
input = sys.stdin.readline
expression = input().strip()
n = len(expression)
arr = []
start, end = 0, 1
for i in range(n):
    if expression[i] == "+":
        arr += [int(expression[start:i]), "+"]
        start = i+1
    elif expression[i] == "-":
        arr += [int(expression[start:i]), "-"]
        start = i+1

arr += [int(expression[start:])]
ans, temp = 0, 0
while arr:
    num = arr.pop()
    if type(num) == int :
        temp += num
    elif num == "-":
        ans -= temp
        temp = 0

ans += temp
print(ans)

뒤에서 부터 식이 나올 때마다 숫자들을 파싱해서 리스트에 넣어주었습니다.

그 후 뒤에서부터 하나씩 빼면서 - 가 나오는 경우를 제외하면 계속 더해주고 -가 나오면 지금까지 더한 것을 ans에 모두 빼주고 temp를 다시 0으로 초기화하여 다음 뺄셈을 대기합니다.

마지막 숫자는 (스택 기준 마지막 숫자, 순서상으로는 첫번째) 부호가 +인 경우 안더해졌을 수도 있으므로 마지막에 temp를 더해줍니다.

 

결과 및 정리

순서대로 풀려고 했는데 방법이 생각나지 않아서 뒤에서 부터 풀어보았는데 답이 보여서 뒤에서 부터 답을 풀었습니다. 그 이유는 첫번째와 마지막은 항상 숫자라서 첫번째는 -가 나오기 전까지 항상 덧셈만 가능한데 저는 이것을 못보고 지나쳐서 첫번째에 -가 오는 경우도 가능하게 풀었습니다. 문제를 제대로 읽지 못했기 때문에 잘한건 아니라고 생각합니다.

import sys
input = sys.stdin.readline
expressions = input().strip()
expressions = expressions.split("-")
ans = 0
expression = expressions[0]
for num in expression.split("+"):
    ans += int(num)
for num in expressions[1:]:
    for n in num.split("+"):
        ans -= int(n)
print(ans)

[55-50+40] 처럼 일반적인 경우라면 의 경우 [55, 50+40] 으로 나누어 첫번째 원소에 그 외 원소들의 합을 빼줍니다. 

[10+20+30+40+50]의 경우라면 10+20+30+40+50 가 첫번째 원소이므로 모든 것을 더한 것이 가장 작은 수입니다.

 

정답은 맞았지만 다른 분들은 어떻게 풀었는지 궁금하였습니다.

저와는 다르게 그리디를 이용하여 풀었는데 split("-")와 split("+")를 이용해서 앞에서부터 계산을 하는 것을 깨닫고 제 방

법보다 가독성이 좋고 간결하여 새롭게 푸는 법을 배웠습니다.