[백준] 1541 - 잃어버린 괄호 (그리디) - 결과 포함

[참고] www.acmicpc.net

그리디 알고리즘 단계

학교다닐 때 뭔가 풀었던 것 같은 기억이 있는 문제였다.

당시에 스택을 공부하면서 풀었던 것 같다.

 

1. 숫자인 경우

2. +인 경우

3. -인 경우

 

세 가지 경우로 나누어 생각했다.

먼저 숫자인 경우는 그대로 스택에 저장한다.

숫자는 연산자가 나왔을 때 자릿수가 정해지므로 연산자가 나오기 전까지는 계속 저장한다.

 

+인 경우는 지금까지 나온 숫자의 자릿수를 결정해주는 역할이다.

+가 나오면 지금까지 저장해오던 숫자의 자릿수만큼 곱해서 숫자를 완성한다.

이 숫자는 sum이라는 변수에 저장한다.

 

-인 경우는 현재 스택의 모든 것을 pop한다고 생각하면 된다.

결국 최종 결과가 가장 작은 수가 되기 위해서는 -가 나온 이후에 모든 값을 빼주어야 최소가 된다.

 

1) 10 + 20 + 30 - 1 인 경우

- 마지막에 - 가 나올때까지 더한 후 1을 빼는 수 밖에 없다.

 

2) 10 - 20 + 30 - 50 인 경우

10 - (20 + 30) - 50 이 가장 최소일 것이다.

 

3) 10 - 20 - 30 + 50

10 - 20 - (30 + 50)이 최소가 된다.

 

결과적으로 - 이후에 모든 값들은 뺄 수 있다.

 

[최종 소스 코드]

n = input()

result = 0
sum = 0
cnt = 0
isMinus = False

stack = list()

for ch in n:
    if '0' <= ch <= '9':
        stack.append(int(ch))
        cnt += 1
    elif ch == '+':
        for s in stack:
            sum += s * (10 ** (cnt - 1))
            cnt -= 1
        stack.clear()
    elif ch == '-':
        if isMinus:
            for s in stack:
                sum += s * (10 ** (cnt - 1))
                cnt -= 1
            result -= sum
        else:
            for s in stack:
                sum += s * (10 ** (cnt - 1))
                cnt -= 1
            result += sum
        sum = 0
        isMinus = True
        stack.clear()

for s in stack:
    sum += s * (10 ** (cnt - 1))
    cnt -= 1

if isMinus:
    result -= sum
else:
    result += sum

print(result)