1541: 잃어버린 괄호

잃어버린 괄호는 +, - 만을 사용한 식에서 괄호를 사용하여 최솟값을 만드는 문제이다.

최솟값을 만드는 핵심은 - 기호가 나왔을 때 그 뒤에 오는 숫자를 가장 크게 만드는 것이다.

숫자를 가장 크게 만들고 그 앞 뒤를 괄호로 감싸게 되면 큰 수 앞에 -가 붙기 때문에 최솟값으로 볼 수 있다.

하지만 - 가 한 개가 아니라 여러 개가 나올 경우도 생각해봐야한다.

이 때는 다음 - 가 나오기 전까지를 괄호로 감싸면 된다.

그러면 다음 - 가 나오기 전까지 숫자를 계속 최대로 만들 수 있기 때문에

한정적인 최댓값을 계속해서 - 값으로 누적시켜 나갈 수가 있다.

 

예를 들면 0-100+20-100+20-100 이라는 식에서 처음 - 이후를 괄호로 감싸게 되면

0-(100+20-100+20-100) 가 되고 결과 값은 60이 된다.

하지만 - 앞을 모두 괄호로 감싸면 0-(100+20)-(100+20)-(100) = -340이 된다.

 

문제 조건에서 입력으로 0으로 시작하는 숫자도 들어올 수 있다고 했기 때문에

들어온 식을 계산 가능한 숫자 형태로 재구성 해서 조건에 맞게 eval을 적용 시켰다.

 

exp = input()
exp_list = list(exp)
 
clean_exp = ""
num_exp = ""
for item in exp_list:
    if item == "+" or item == "-":
        clean_exp += str(int(num_exp)) + item
        num_exp = ""
    else:
        num_exp += item
 
clean_exp += str(int(num_exp))
 
if '-' in clean_exp:
    clean_exp_list = clean_exp.split('-')
 
    exp = ""
    for item in clean_exp_list:
        exp += "(" + item + ")-"
    exp = exp[:-1]
    result = eval(exp)
else:
    result = eval(clean_exp)
 
print(result)