[10773] 제로

 

백준 Silver IV | 10773 | Python | 문제 링크

문제 설명

나코더 기장 재민이는 동생 재훈이에게 수학을 가르치고 있다. 재민이가 수를 쓰다가 실수를 하면 지우개로 지운다. 재민이가 실수를 한 경우에는 0을 쓴다. 0이 쓰여지면 가장 최근에 쓴 수를 지운다. 재민이가 쓴 모든 수의 합을 구하라.

입력

첫째 줄에 K가 주어진다. (1 ≤ K ≤ 100,000) 이후 K개의 줄에 정수가 하나씩 주어진다. 정수는 0에서 1,000,000 사이의 값이며, 정수가 0인 경우에는 가장 최근에 쓴 수를 지운다. 0을 제외한 나머지 수는 최소 하나 이상 존재한다.

출력

재민이가 최종적으로 적어 놓은 수의 합을 출력한다.

입출력 예

입력	출력
4 3 0 4 0	0

 

나의 풀이

풀이 1 - 틀린 코드와 반례 추적

import sys
input = sys.stdin.readline
num = int(input())
stack = []
for _ in range(num):
    n = int(input())
    if n == 0 and stack:
        stack.pop()
    stack.append(n)
print(sum(stack))

제출하고 맞았다. 그냥 넘어갔다.

그런데 코드를 다시 보다가 뭔가 눈에 걸렸다. if n == 0인 경우 pop을 하고 있는데, 그 아래 stack.append(n)이 조건 바깥에 있었다. if 블록 안이 아니라 그냥 for 루프 안이었다. 0을 pop하고 나서 다시 0을 push하고 있었던 것이다.

"아, 근데 0은 합산에 영향이 없으니까 괜찮지 않나?"

순간 그런 생각이 들었다. 0을 더해도 합은 바뀌지 않으니, 스택에 0이 들어있든 말든 최종 결과는 같다고 생각했다. 그냥 넘어가기가 어려웠다.

1, 2, 0, 0을 직접 넣어봤다. 1과 2를 쌓고, 0 두 개가 연속으로 들어오는 경우다.

버그 있는 코드로 추적하면:

n=1 → push      stack = [1]
n=2 → push      stack = [1, 2]
n=0 → pop 2, push 0  stack = [1, 0]
n=0 → pop 0, push 0  stack = [1, 0]
sum = 1

정답은 0이어야 한다. 1과 2를 쌓고, 0 두 개가 2와 1을 순서대로 지우는 것이니까. 그런데 코드 결과는 1이 나왔다.

세 번째 입력에서 2를 pop하고 0을 push했다. 그러면 스택에 [1, 0]이 남는다. 네 번째 입력인 0이 들어왔을 때, pop 대상은 0이 된다. 1은 건드리지도 못한 채로 끝났다.

0이 합산에 영향이 없다는 생각은 맞았다. 하지만 0이 스택에서 자리를 차지한다는 것은 빠뜨리고 있었다. 0을 push하는 순간, 그 0은 다음 0의 pop 대상이 된다. 2가 지워져야 할 자리를 0이 막아버리는 것이다.

첫 제출이 통과된 건 운이 좋았던 것이다. 테스트케이스에 0이 연속으로 등장하는 경우가 없었던 것이다. 0이 한 번씩만 나왔다면, 0을 pop하고 0을 push해도 다음 0이 없으니 문제가 드러나지 않는다.

풀이 2 - 최종 제출 코드

import sys
input = sys.stdin.readline

num = int(input())
stack = []

for _ in range(num):
    n = int(input())
    if n == 0:
        stack.pop()
    else:
        stack.append(n)

print(sum(stack))

0은 "이전 수를 지워라"는 명령이지, 스택에 넣을 값이 아니다. if/else로 두 경우를 명확히 분리하면 된다.

최초 제출 코드에서 if n == 0 and stack: 이라고 쓴 것은 방어적으로 체크한 것이었는데, 이 문제는 "0이 입력될 경우 스택이 비어있는 경우는 없다"고 보장하기 때문에 and stack은 생략해도 된다.