[백준-11279,1927] 최대힙, 최소힙 #힙

1. 백준-11279 최대힙, 1927 최소힙

https://www.acmicpc.net/problem/11279

https://www.acmicpc.net/problem/1927

2. 알고리즘 카테고리 : 힙

---

3. 나의 풀이 알고리즘(1차) : 힙

import heapq

max_heap = []
input_count = int(input())

for _ in range(input_count):
    i = int(input())
    if i == 0:
        if len(max_heap) == 0:
            print(int(i))
        else:
            print(-heapq.heappop(max_heap))
    else:
        heapq.heappush(max_heap, -i)

- 여기서 시간초과 문제가 발생하였다. N이 10^5이고, N에 대하여 heappop NlogN, heappush NlogN이기 때문에 시간 복잡도에서 문제가 없었다. 코드에 문제가 없다면 외부에서 데이터를 불러오는 과정에서 시간이 초과되는 것이라고 유추를 해볼 수 있다.

- 찾아보았더니 input() 내장함수 자체가 문자열로 변환, strip을 수행한 뒤 반환하기 때문에 느리다는 것을 알게 되었다. 따라서 sys.stdin과 readline으로 수행하도록 코드를 수정하였다.

 

나의 풀이 알고리즘(2차) : 힙

import heapq
import sys

lines = []
for line in sys.stdin:
    lines.append(line)
lines.reverse()

max_heap = []
input_count = int(lines.pop())


for _ in range(input_count):
    print(f'max_heap: {max_heap}')
    i = int(lines.pop())
    if i == 0:
        if len(max_heap) == 0:
            print(0)
        else:
            print(-heapq.heappop(max_heap))
    else:
        heapq.heappush(max_heap, -i)