백준 실버2 1541. 잃어버린 괄호 (python)

잃어버린 괄호

풀이

+와 -로만 이루어진 숫자 연산 문자열이 주어지고, 이를 이용해서 가장 적은 수가 나올 수 있게 괄호를 치고 그 값을 출력하는 문제이다.

예시로

55-50+40 = 45
55-(50+40) = -35

위와 같은 방식으로 괄호를 치는 것이다.
이경우는 저 방법 이외에 더 작게 만들 방법이 없으므로 가장 작은 값은 -35가 된다.

위의 예제를 포함해서 다른 것들도 생각해 보면 결국 값을 최소화하는 것은 음수로 만들어줘야 하고 제일 큰 값을 빼게 만드는 방법은 괄호를 -이후에 다 넣어주는 방법이다.

그렇지만 -가 등장하자마자 뒤의 모든 값을 한 번에 괄호치면 안 되고
-와 - 사이의 값만을 적절히 괄호 쳐줘야 된다.

35+45-25+50+620-112+51-455-452+2225+25
35+45-(25+50+620)-(112+51)-(455)-(452+2225+25)

이런 식으로 괄호를 친다는 것이다.

이러함을 생각하고 문제를 풀었다.

1. 주어진 문자열 입력받기
2. 연산자와 숫자 분리하기
3. 합을 위한 준비
4. -와-사이의 값들을 합치기. 만약 - 가 없다면 그냥 일단 합치기. 이 값을 압수에 -가 있었는지 여부에 따라 -1을 곱해주고 어떤 리스트에 저장해 두기
5. 구한 모든 값을 출력

-일 경우에만 관련해서 생각하면 되는데 +연산자의 경우 그냥 합치기만 하면 되는 것이고 괄호에 대해서도 신경 쓰지 않아도 되기에 그렇다.

하지만 -의 경우에는 이전 값들의 종료하고 괄호를 쳐서 합친 값을 리스트에 저장시키고 만약 괄호 앞에 마이너스가 있었다면 -1을 곱해주고 저장시키는 것도 생각해야 되기에 아래처럼 코드를 작성했다.

else:
        # -를 만났으니 이전까지 합했던 값을 집어넣기
        if lst[i] == '-':
            if is_minus== True:
                value_list.append(value*-1)
            else:
                value_list.append(value)
            # 한번 마이너스를 만난 뒤에 굳이 False로 바꿀 필요 없음.
            is_minus = True
            value = 0

또한 연산의 마지막에는 -나 +와 같은 연산자가 없이 숫자로 끝나기에 아래와 같은 코드도 입력해 주었다.

if i == (len(lst)-1):
            if is_minus== True:
                value_list.append(value*-1)
            else:
                value_list.append(value)

이런 결과 아래와 같은 코드가 작성되었고, 제출하니 통과되었다.

import sys
S = sys.stdin.readline().strip()
S = S + '.'
lst = []
tmp = ''
for i in range(len(S)):
    if S[i] != '.' and S[i] !='+' and S[i] !='-':
        tmp += S[i]
    else:
        lst.append(int(tmp))
        tmp=''
        if S[i] !='.':
            lst.append(S[i])

# -이후 에 괄호를 작용시켜보자.
# 괄호안의 값들의 합을 value로 저장
value = 0
# 모든 괄호 값들을 합한 것을 value_list에 저장
value_list = []
is_minus = False
for i in range(len(lst)):
    # 연산자가 아니면 is_minus에 입력
    if lst[i] != '+' and lst[i] != '-':
        value += lst[i]
        # 마지막 값이면 -를 만나지 않을테니 value_list에 입력
        if i == (len(lst)-1):
            if is_minus== True:
                value_list.append(value*-1)
            else:
                value_list.append(value)
    # 연산자를 만나면
    # -와 -사이에서 합하고 value_list에 집어넣기
    else:
        # -를 만났으니 이전까지 합했던 값을 집어넣기
        if lst[i] == '-':
            if is_minus== True:
                value_list.append(value*-1)
            else:
                value_list.append(value)
            # 한번 마이너스를 만난 뒤에 굳이 False로 바꿀 필요 없음.
            is_minus = True
            value = 0
print(sum(value_list))