[baekjoon] 백준 11279번(파이썬)

[문제]

[SOL 1]

import sys
input = sys.stdin.readline
from collections import deque

heap = deque()
N = int(input())

for _ in range(N):
    num = int(input())
    
    if(num==0):
        if(len(heap)==0): # 배열이 비어 있는 경우 0을 출력한다.
            print(0)
        else:
            result = heap.popleft()
            print(result)
   #배열에서 가장 큰 값을 출력하고 그 값을 배열에서 제거한다.
        
    #입력을 받은 다음 정렬을 통해 큰 수부터 배열을 하고 제일 앞에 값을 pop한다.
    else:
        heap.append(num)
        for i in range(len(heap), 0, -1):
            
            for j in range(i-1,0,-1):
                tmp = 0
                if(heap[j]>heap[j-1]):
                    tmp = heap[j-1]
                    heap[j-1] = heap[j]
                    heap[j] = tmp
                else:
                    break

그냥 풀었다. 이중 for문을 사용하여 시간 초과가 뜰 거 같더라니 역시 시간 초과가 떴다.

[SOL 2]

import sys
import heapq

heap = []
n = int(sys.stdin.readline())
for _ in range(n):
  m = int(sys.stdin.readline())
  if m == 0:
    if len(heap) == 0:
      print(0)
    else:
      print((-1)*heapq.heappop(heap))
  else:
    heapq.heappush(heap, (-1)*m)

힙 자료구조를 파이썬 내장모듈로 구현할 수 있다는 것을 배웠다.

기본 모델은 최소힙인데 -1을 곱해줌으로서 최대힙으로 바꿨다.