백준 1927번 바로가기

첫 번째 시도

# 입력
import sys
read = sys.stdin.readline
n = int(read().strip())
arr = []

# 처리
for _ in range(n):
  x = int(read().strip())
  if x == 0:
    try:
      print(arr.pop())
    except:
      print(0)
  else:
    arr.append(x)
  arr.sort(reverse=True)

최종 제출

# 입력
import heapq
n,*l = open(0)
heap = []

# 처리
for x in l:
  if (x:=int(x)) == 0:
    try:
      print(heapq.heappop(heap))
    except:
      print(0)
  else:
    heapq.heappush(heap,x)

CODE REVIEW

  1. 자료구조와 우선순위 큐의 구현 방법에 따른 시간 복잡도는 링크 참조!
  2. 우선순위 큐를 구현하는 방법에는 여러가지가 있는데, 배열이나 연결 리스트를 이용할 경우 시간 복잡도가 (삽입,삭제) = (O(1),O(n)) 혹은 (O(n),O(1))로 나타난다.
  3. 삽입, 삭제를 모두 구현해야하는 이 문제에서는 O(n)의 시간복잡도는 시간초과 에러를 발생시킬 수 밖에 없다. 게다가 매번 x가 들어올 때마다 arr을 새로 정렬하니까 시간이 많이 걸릴 수 밖에.. 삽입할 때 오름차순을 헤치지 않는 알맞은 자리에 집어넣어야 시간을 절약할 수 있다.
  4. 따라서 삽입, 삭제 모두 시간복잡도가 O(logn)인 힙(heap)을 이용해서 우선순위 큐(priority queue)를 구현해보자.
  5. 힙(heap)을 스스로 구현하려다가 귀찮아서(…) 그냥 python에서 제공하는 heapq - 힙 큐 알고리즘을 이용했다.
    • heapq 모듈의 documentation에 따르면…
    • 삽입: heapq.heappush(heap, item)
    • 삭제: heapq.heappop(item) 만일 힙이 비어있으면 IndexError 발생.
  6. heapq라는 매우 유용한 python 내장 모듈이 있음을 기억해두고, 최댓값/최솟값을 다루는 문제가 있다면 유용하게 써먹자!!