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

문제 정보

제목 : 잃어버린 괄호

번호 : 1541번

사용 언어 : Python

문제 링크

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

1541번: 잃어버린 괄호

 

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

 

문제

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

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

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

 

입력

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

 

출력

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

 

입출력 예제

---

나의 풀이

실패한 풀이

 -를 기준으로 연산을 진행하면 될 것같아서 -를 높은 우선순위로 두고 후위표기식으로 변환하여 계산했습니다. 하지만 이것은 -가 연속으로 나올 때 값이 다르게 나온다는 문제가 있었습니다. 문제를 너무 어렵게 생각했던 것이 오답의 원인이었던것 같습니다.

math = input()
math_list = []
stack = []
tmp = ""

# +와 -를 우선순위를 나누어 후위표기식으로 변환함
for i in math :
    if (i == "+" or i == "-") :
        if ( i == "-" ) :
            while stack and stack[-1] != "-" :
                math_list.append(stack.pop())
        stack.append(i)
        math_list.append(int(tmp))
        tmp = ""
    else :
        tmp += i
math_list.append( int(tmp))
while(stack) :
    math_list.append( stack.pop() )

# 후위표기식에 따른 계산
index = 0
while(len(math_list) != 1) :
    if math_list[index] == "+" or math_list[index] == "-" :
        if math_list[index] == "+" :
            math_list[index] = math_list[index-2] + math_list[index-1]
        else :
            math_list[index] = math_list[index-2] - math_list[index-1]
        math_list.pop(index-2)
        math_list.pop(index-2)
        index = 0
    else :
        index += 1

print(math_list[0])

 

다른 방법

잘 안풀려서 찾아보던중 이 문제를 해결할 간단한 방법을 찾게 되었습니다. 식을 '-'를 기준으로 나누어 math리스트에 저장합니다.

math의 요소만큼 반복하는 for루프를 생성하고, 각 요소를 +를 기준으로 나누어 tmp리스트에 저장합니다. 그리고 tmp리스트의 요소를 정수형으로 변환 후 합을 구해 math_list 리스트에 추가합니다.

for m in math :
    sum = 0
    tmp = m.split("+") # +를 기준으로 분리하여 각 요소들의 합을 구하여 계산할 리스트에 추가함
    for t in tmp :
        sum += int(t)
    math_list.append(sum)

위의 반복이 끝나면 answer에는 math_list의 처음 요소를 저장합니다. 처음 나오는 수는 무조건 양수이기 때문입니다. 이후 math_list에 순차적으로 접근하며 answer에서 각 요소를 뺍니다. 모든 과정을 거친 후 answer을 출력합니다.

answer = math_list.pop(0)
for m in math_list :
    answer -= m
print(answer)

 

전체 코드

math = input().split("-")
math_list = []

for m in math :
    sum = 0
    tmp = m.split("+") # +를 기준으로 분리하여 각 요소들의 합을 구하여 계산할 리스트에 추가함
    for t in tmp :
        sum += int(t)
    math_list.append(sum)

answer = math_list.pop(0)
for m in math_list :
    answer -= m
print(answer)