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

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

1541번: 잃어버린 괄호

 

문제

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

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

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

 

입력

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

 

출력

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

 

 

풀이

이 문제는 - 가 나오는 순간 다음 -가 나올 때까지 괄호를 치는 것이 가장 작은 수를 만들 수 있다.

 

1번째 풀이

import sys

exp = list(map(str, sys.stdin.readline().strip()))
answer = 0
flag = False
temp = []


for i in exp:
    if i == '-' and flag is False:
        temp.append('-')
        temp.append('(')
        flag = True
    elif i == '-' and flag is True:
        temp.append(')')
        temp.append('-')
        temp.append('(')
    else:
        temp.append(i)

if flag is True:
    temp.append(')')

print(eval(''.join(temp)))

먼저 실제 '('를 식에 넣는 것을 가정하여 구현을 했었다.

처음 -가 나오면 - ( 를 넣고 그 이외의 경우에는 ) - ( 를 넣는 것으로 괄호를 넣고
-가 1번이라도 나온적 있으면 마지막에 )를 넣어줘서 괄호를 완성해줬다.

SyntacError가 나왔는데 수가 0으로 시작할 수 있다는 조건을 처리하지 않았기 때문에 101-01과 같은 식을 파이썬 eval에서 처리할 수 없어서 난 문제였다.

 

1번째 풀이 수정

import sys

exp = list(map(str, sys.stdin.readline().strip()))
flag = False
temp = []
zero_flag = False
## zero_flag = True로 바꾸면 정상 작동 but 코드가 복잡하고 길다.


for i in exp:
    if i == '-' and flag is False:
        flag = True
        temp.append('-')
        temp.append('(')
        zero_flag = True
    elif i == '-' and flag is True:
        temp.append(')')
        temp.append('-')
        temp.append('(')
        zero_flag = True
    elif i == '+':
        zero_flag = True
        temp.append('+')
    elif zero_flag is True and i == '0':
        continue
    else:
        zero_flag = False
        temp.append(i)

if flag is True:
    temp.append(')')

print(eval(''.join(temp)))

+, -와 같은 연산자가 나온 직후에 0이 나오면 continue를 통하여 무시하고 지나가는 것으로
0으로 시작하는 숫자를 제거해줬다.

 

하지만 이 경우에도 Syntax error가 처음 나왔었는데 이유를 몰랐다.
블로그에 글을 정리하면서 발견했는데 처음 숫자가 0으로 시작되는 경우를 체크를 하지 못했기 때문이다. 

 

zero_flag의 초기값을 False로 줬는데 처음부터 True로 주는 것으로 처음 등장하는 0들도 제거하면 문제없이 작동하는 것을 확인했다.

 

최종 풀이 

1번째 풀이 수정본에서 syntax error의 원인을 찾지 못해서 로직 자체를 수정했다.
( 를 직접 넣는다거나 하지 않고 -를 기준으로 문자열을 구분 짓는 것으로 풀이했다.

exp = sys.stdin.readline().lstrip().rstrip()
exp = exp.split('-')
answer = 0

for idx, v in enumerate(exp):
    exp[idx] = v.split('+')

입력 받은 문자열을 - 기준으로 구분짓고 -로 구분된 문자열들을 다시 +를 기준으로 구분한다.

이렇게되면 데이터가 2차원 리스트 형식으로 들어가게 되는데
입력이 55-50+40이라면 [[55], [50, 40]]가 나오게 된다. 이 경우에 0번에 있는 리스트의 값은 양수이고 나머지 모든 값은
음수이기 때문에 해당 방법을 구현하면

for i in exp[0]:
    answer += int(i)

for i in exp[1:]:
    for j in i:
        answer -= int(j)

print(answer)

0번에 존재하는 항목들은 모두 answer에 + 연산
1번부터 존재하는 항목들은 모두 - 연산을 하면 된다. 01, 0001과 같은 문자열은 int 형변환을 이용하여 처리했다.

 

 

전체 코드

import sys

exp = sys.stdin.readline().lstrip().rstrip()
exp = exp.split('-')
answer = 0

for idx, v in enumerate(exp):
    exp[idx] = v.split('+')

for i in exp[0]:
    answer += int(i)

for i in exp[1:]:
    for j in i:
        answer -= int(j)

print(answer)

1번째 풀이 방법 같은 경우에는 조금 더 다듬어서 실제로 괄호를 넣어야하는 경우에 전처리 과정으로 사용할 수 있을 것 같다.