[백준] 2075 N 번째 큰 수 - python

문제 링크

이 문제는 N번째 큰 수를 찾는 것이기 때문에 heapq 라이브러리를 사용해야 한다는 것을 금방 알 수 있었다.

그러나 이 문제는 메모리 초과가 문제였다.

따라서 N번째 큰 수를 찾는 것이기 때문에 heap의 길이를 작게 고정시켜서 문제를 해결하려고 노력해야 했어야 했다.

N번째까지만 큰 수로 정렬하면 되기 때문에 heap의 길이를 N으로 유지시켰다.

heapq.heappush(heap, i)
    if len(heap) > n:
        heapq.heappop(heap)

이런 식으로 일단 heap에 수를 집어넣은 후, 길이가 N을 넘어가면 pop으로 가장 작은 수를 삭제하였다.

이것이 가능한 이유는 기본적으로 python의 heapq 라이브러리는 min heap을 지원하기 때문이다.
heap은 완전 이진 노드이다. 이는 자식 노드가 무조건 부모 노드보다 크다는 소리이다.
일단 heap에 집어넣고, pop을 하여 heap의 길이를 N으로 맞춰주면, heap의 최상위 부모 노드는 항상 N번째 큰 수로 고정된다.

아래는 최종 코드이다.

# N번째 큰 수
import sys
import heapq

n = int(sys.stdin.readline().rstrip())

heap = []

# 메모리 초과...
for _ in range(n):
    t = list(map(int, sys.stdin.readline().rstrip().split(' ')))
    for i in t:
        heapq.heappush(heap, i)
        if len(heap) > n:
            heapq.heappop(heap)

result = heapq.heappop(heap)

print(result)