백준 10773. 제로

문제 설명

0을 외칠 경우 가장 최근에 쓴 수가 지워진다.

지워진 수를 제외한 모든 수를 받아 적은 후, 그 수의 합을 구해보자.

 

입력

첫 번째 줄에 정수 K가 주어진다.

이후 K개의 줄에 정수가 하나씩 주어지고, 정수는 0에서 1,000,000사이의 값을 가지며,

정수가 0인 경우에는 최근에 쓴 수를 지우고, 아닐 경우에 해당 수를 쓴다.

(정수가 0인 경우 지울 수 있는 수가 있음을 보장한다.)

 

출력

최종적으로 적어낸 수의 합을 출력

 

N = int(input())
num = []
for i in range(N):
    x = int(input())
    if x == 0:
        num.pop()
    else:
        num.append(x)

print(sum(num))

 

시간 제한이 1초인데, 입력으로 주어지는 N은 100,000(십만) 이하이므로

O(N)의 시간 복잡도로 해결 가능하다.