[파이썬] 백준 10773번 : 제로

[문제]

백준 10773번 제로

 

 

 

[구현]

• 문제 핵심
  • 정수 K개가 순서대로 주어지고,
  • 숫자가 "0"이면 가장 최근에 적은 수를 지움
  • 아닌 경우 스택에 계속 적재
  • 마지막에 스택에 남은 수를 모두 더한 값이 정답

 

• 구현 방법
  • 최근에 입력된 수를 제거해야 하므로 "스택(stack)"이 적절하다고 판단
  • 숫자가 0일 경우 stack.pop()으로 최근 수 제거
  • 숫자가 0이 아니면 stack.append()로 입력값 저장
  • 모든 입력이 끝난 뒤 sum(stack)으로 결과 계산

 

 

 

[코드]

# 리스트를 스택처럼 사용해서 풀었음
import sys

input = sys.stdin.readline
K = int(input())
stack = []

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

print(sum(stack))

 

 

 

[제출 결과]

 

 

 

[시간복잡도]

for _ in range(K):
    num = int(input())
    ...
print(sum(stack))

• 입력 수 K에 대해 한 번씩만 순회 : O(K)
• append(), pop()은 모두 O(1)
• 마지막에 sum(stack)도 최악의 경우 K개의 숫자를 합산 : O(K)

총 시간복잡도: O(K)

 

 

 

[다른 접근 방법]

• 배열 인덱스 조작
  • 구현 복잡해서 안했음
• deque
  • 이 문제에서는 단순히 뒤에서만 삽입/삭제하므로 list로 충분함

 

 

 

[회고]

"가장 나중에 적은 수를 지우는 행동" 때문에 자연스럽게 LIFO(Last-In-First-Out) 구조인 스택을 사용했다.