1541 - 잃어버린 괄호 (Python)

문제

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

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

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

 

입력

첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다.

그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 많이 연속되는 숫자는 없다.

수는 0으로 시작할 수 있다. 입력으로 주어지는 식의 길이는 50보다 작거나 같다.

 

예제 입력

55-50+40

출력

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

 

예제 출력

-35

 

분석

문제를 잘 보면 연산자가 +와 -만으로 제한되어 있으며, 최소값을 출력하는 문제입니다.

 

예제로 파악할 수 있겠지만, - 가 나오는 순간 뒤에 +가 나오든 -가 나오든 모두 -로 치부할 수 있다는 말입니다.

-50 + 50 + 30 +20 -34 -52 

->

-(50 + 50 + 30 + 20) -34 -52

양수에는 괄호에 포함시켜주면 되고 마이너스는 그대로 놔두면 됩니다.

 

반례 모음

문제가 단순하여, 반례가 나오기 쉬우므로 반례를 일으키는 입력값들을 산정하여 모아보았습니다.

 

임력

-> 출력


5+065

-> 70


12

-> 12


00000+00000+00000+00000+00000+00000+00000+00000+0

-> 0


0-101-01

-> -102

 

풀이

연산자 "-"가 나오기 전에는 양수 배열에 포함 시키다가, "-"가 등장하면 모두 음수의 배열에 포함시켜

최솟값을 산정하는 식으로 풀이하였습니다.

 

PyCharm 캡쳐

입력값으로 반복적으로 "+" 인지, "-"인지, 숫자인지 검사하고,

연산자 "-"가 나오기 전까지는 plus_array에 포함하여 + 연산을 수행하지만

 

"-"가 나오는 순간 그 뒤의 연산자를 제외한 숫자를 모두 절댓값으로 minus_array에 포함시켜 

plus_array - minus_array로 최소값을 도출하였습니다.

 

소스 코드

import sys

ab = sys.stdin.readline()

tempString = ""
plus_array = []
minus_array = []

i = 0

while i < len(ab) - 1:
    if ab[i] == "-":
        temp_array = ab[i + 1:].replace("+", "-")
        minus_array = list(map(int, temp_array.split("-")))
        break
    elif ab[i] == "+":
        plus_array.append(int(tempString))
        tempString = ""
    else:
        tempString += ab[i]
    i += 1

if len(tempString) > 0:
    plus_array.append(int(tempString))

print(sum(plus_array) - sum(minus_array))