[코테] 백준 그리디 1541번 문제

1541번 : 잃어버린 괄호

문제 링크

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

문제

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

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

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

입력

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

출력

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

문제 풀이

# 문자열을 정규식으로 분리하기 위해 re모듈 import
import re

# 입력받은 문자열을 부호는 mark_arr에 숫자는 num_arr에 분리하여 저장
string = input()
mark_arr = re.findall(r'-|\+', string)
num_arr = list(map(int, re.split(r'-|\+', string)))

# case1. 부호가 없는 숫자만 있는 문자열일 경우 결과는 num_arr 첫번째 항목
if len(mark_arr) == 0 : result = num_arr[0]

# case2. - 부호가 없으면 num_arr 항목들을 sum 집계
elif '-' not in mark_arr : result = sum(num_arr)

# case3. - 부호도 포함된 배열일 경우
else : 
    # 일단 처음 부호가 +, - 인지 확인하여 num_arr 첫번째와 두번째 항목 집계
    if mark_arr[0] == '+' : result = num_arr[0] + num_arr[1]
    else : result = num_arr[0] - num_arr[1]
        
    # - 부호의 위치를 찾고, mark_arr의 해당 위치 뒤로는 다 -로 치환
    # - 부호가 나온 시점부터는 뒤에 부호와 상관없이 괄호로 묶어서 최소값 처리할 수 있기 때문
    idx = mark_arr.index('-')
    mark_arr[idx:] = ['-'] * (len(mark_arr) - idx)
    
    # mark_arr의 부호를 확인하여 num_arr 나머지 항목들 집계 
    for i in range(1, len(mark_arr)) :
        if mark_arr[i] == '+' : result += num_arr[i+1]
        else : result -= num_arr[i+1]

print(result)