[백준][그리디 알고리즘][파이썬] 1541.잃어버린 괄호

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

1541번: 잃어버린 괄호

 

세준이는 양수와 +, -, 그리고 괄호를 가지고 식을 만들었다가 괄호를 모두 지웠다고 한다. 그리고 식의 값이 최소가 되도록 괄호를 사용하고 싶어한다. 세준이를 도와주자.

 

예를 들어 55-50+40을 최소로 만들기 위해서는 55-(50+40) 이렇게 괄호를 사용해야한다. 그럼 식의 값은 -35가 된다.

최소값으로 만들어야하니까 괄호를 사용해 양수를 음수로 바꿔주면 될 것같다.

따라서 -가 나오면 괄호를 열어주고, 그 다음 -가 나오면 괄호를 닫아주면 최소값이 될 것이다.

 

import sys
N = sys.stdin.readline()
 
count = 0
index_minus = N.find('-')
if index_minus != -1:
    for i in range(index_minus, len(N)):
        if N[i] == '+':
            count += 1
 
    N = N[::-1]
    N = N.replace('+','-',count)
    N = N[::-1]
    print(eval(N))
else:
    print(eval(N))

 

런타임 에러가 나는데 이유는 잘 모르겠다..

 

한참을 생각해도 모르겠어서 문제를 다시 보니까 '수는 0으로 시작할 수 있다'는 조건이 보였다.. 그리고 숫자가 0으로 시작하면 eval()을 사용했을 때 계산이 안된다는 것을 알고 이 부분 때문에 런타임에러가 난다는 것을 알았다..

 

그래서 어떻게 해야할 지 고민하다가 모르겠어서 구글링으로 다른 사람의 코드를 읽고 이해한 후 주석을 달아보았다..

 

def _1541():
    N = str(input())
    arr = N.split('-') # -를 기준으로 식을 나눠서 arr에 저장한다.
    # 식에 -가 없는 경우 => 그냥 다 더해주면 됌
    if len(arr) == 1:
        ret = 0
        arr = N.split('+')
        for i in range(len(arr)):
            ret += int(arr[i])
        print(ret)
        return
 
    # 식에 -가 있는 경우 => 4가지의 경우로 나누어 생각한다.
    ret = 0
    for i in range(len(arr)):
        # 1. i가 0이고(-의 왼쪽 식) 왼쪽식에 +가 없는 경우 => int로 바꾸어 모두 더해주면 됌.(0으로 시작하는 숫자에서 0을 없애기 위함!)
        if '+' not in arr[i] and i == 0:
            ret += int(arr[i])
        # 2. i가 0이고(-의 왼쪽 식) 왼쪽식에 +가 있는 경우 => +를 기준으로 식을 나누고 int로 바꾸어 모두 더해줌(0으로 시작하는 숫자에서 0을 없애기 위함!)
        elif '+' in arr[i] and i == 0:
            temp = arr[i].split('+')
            for j in range(len(temp)):
                ret += int(temp[j])
        # 3. i가 0이 아니고(-의 오른쪽 식) 오른쪽식에 +가 있는 경우 => +를 기준으로 식을 나누고 int로 바꾸어 모두 더해줌(0으로 시작하는 숫자에서 0을 없애기 위함!)
        elif '+' in arr[i] and i != 0:
            temp = arr[i].split('+')
            for j in range(len(temp)):
                ret -= int(temp[j])
        # 4. i가 0이 아니고(-의 오른쪽 식) 오른쪽식에 +가 없는 경우 => int로 바꾸어 모두 더해주면 됌.(0으로 시작하는 숫자에서 0을 없애기 위함!)
        else:
            ret -= int(arr[i])
    print(ret)
 
_1541()

 

참고: https://has3ong.tistory.com/613