잃어버린 괄호

풀이

 처음에는 완전 탐색으로 접근했다. 하지만 생각보다 구현하기가 어려워 다른 방법이 있는지 생각해봤고 그리디 방식으로 우회해 풀었다. 그리디 관점에서 생각하면 쉽게 풀 수 있는 문제다. 가장 작은 최솟값을 만들기 위해서는 가능한 큰 수를 빼야 한다. 수식이 더하기와 빼기 연산만으로 이뤄져 있기 때문에 더하기에 해당하는 부분에 괄호를 쳐서 먼저 모두 계산한 후 빼기를 실행하면 된다.

 나는 좀 어렵게 풀었는데 모범답안은 아래와 같다.

1. answer를 0으로 초기화
2. 들어온 데이터를 '-' 기호를 기준으로 split() 수행하기
3. 덩어리마다 합 구하기
   4.1 if(가장 앞 덩어리) -> answer에 합 더하기
   4.2 else -> answer에 합 빼기

S = input()

tem = ''
total = 0
flag = False
for i in range(len(S)):
    if S[i] != '+' and S[i] != '-':
        tem += S[i]
    # 괄호 X
    elif flag == False:
        if S[i] == '-':
            flag = True
        total += int(tem)
        tem = ''
    # 괄호 O
    elif flag == True:
        total -= int(tem)
        tem = ''
# 마지막 숫자 계산
if flag == False:
    total += int(tem)
else:
    total -= int(tem)
print(total)

시간복잡도 : O(N) (N:문자열 S의 길이)