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

• Problem Link : https://www.acmicpc.net/problem/1541

문제

• +, - 연산자로만 구성된 식이 들어온다.
• 해당 식의 결과값이 최소가 되도록 괄호를 친다고 할 때 최소값을 구하여라

입력

• 첫째 줄, 식이 주어진다.
• 식은 '0'~'9'와 '+','-'로만 이루어져있으면 첫 문자와 마지막 문자는 숫자이다.
• 연속해서 두 개 이상의 연산자는 없다.

출력

• 첫째 줄, 최소 결과값을 출력한다.

풀이

문자열로 식이 그대로 입력으로 들어오면 숫자와 연산자를 구분하는, parsing을 이용하면 간단히 해결할 수 있는 문제이다.

• 숫자 : '-'와 '+'를 구분자로 사용하여 분리
• 연산자 : '0'~'9'를 구분자로 사용하여 분리

원래는 split으로 구분자를 이용해서 분리할 수 있으나 이렇게 구분자를 여러개 사용해서 분리하려면 정규 표현식을 사용하면 굉장히 편리하게 해결할 수 있다.

정규 표현식에 관련되 설명은 이 문서를 참고하자.

re.split(pattern, string) 함수?

파이썬에서 제공하는 정규 표현식 모듈 re에서 제공하는 문자 구분 함수로 pattern에 해당하는 구분자를 이용해 string을 분해한다. 따라서 아래와 같이 숫자와 연산자를 구분하는 코드를 작성할 수 있다.

num = list(map(int, re.split("[-+]", s)))
oper = [i for i in re.split("[0-9]", s) if i in ["+", "-"]]

연산자 구분에서 for~if 문을 추가로 작성해준 이유는 '009'처럼 세 자리 숫자가 들어오면 숫자와 숫자를 자를 때 한자리씩 잘라서 ''와 같이 아무것도 없는 문자가 추가된다. 패턴을 [0-9]+ 로 숫자의 반복으로 수정을 해줘도 숫자와 '+', '-' 사이에 있는 '' 문자가 추가된다. 따라서 우리에게 필요한 '-'와 '+'를 걸러내주기 위해 for~if문을 사용했다.

숫자는 이런 과정이 필요없는 이유?

• 연산자를 구분자로 해서 slipt 시키면 숫자만 정상적으로 잘 구분 된다. 아마도 연산자를 기준으로 숫자들끼리 구분할 때 연산자의 앞 뒤의 '' 문자가 숫자들과 함께 붙어서 '55' + '' - '55' 처럼 '' 문자가 자연스럽게 날라가는 것 같다.

• re.split을 사용해서 분리할 때에는 꼭 출력해서 확인을 해보고 필요한 문자만 걸러내는 과정이 필요한 지를 확인하자.

이제 숫자와 연산자 분리가 끝났으므로 식의 결과가 최소가 되도록 괄호를 만들었다고 생각해보자. 간단히 생각하면 '-' 부호 뒤의 '+'들을 괄호로 묶어서 최대한 큰 수를 빼면 식의 값을 최소값이 된다. 이를 괄호를 풀면 괄호 안에 있던 '+' 연사자들은 '-' 부호로 변한다.

따라서 '-' 부호 뒤의 연속으로 나오는 '+' 연산자를 모두 '-' 연산자로 바꾼 후 식의 계산을 진행하면 최소값을 손쉽게 구할 수 있다.

코드

import sys
import re

input = sys.stdin.readline

s = input()[:-1]
num = list(map(int, re.split("[-+]", s)))
oper = [i for i in re.split("[0-9]", s) if i in ["+", "-"]]

i = 0
while i < len(oper):
    if oper[i] == "-":
        while i + 1 < len(oper) and oper[i + 1] == "+":
            oper[i + 1] = "-"
            i += 1
    i += 1

ans = num[0]
num = num[1:]

for i in range(len(num)):
    ans = ans + num[i] if oper[i] == "+" else ans - num[i]

print(ans)