[BOJ 2075] N번째 큰 수(Python)

문제

N번째 큰 수

---

문제 해설

메모리를 감안하여 문제를 푸는 것에 익숙치 않아 처음 시도때 실패했습니다. 모든 숫자를 최대 힙에 담아 n번째 나오는 숫자로 답을 구하는 방식이었습니다.

1500 * 1500만큼의 숫자가 힙에 들어가기 때문에 12MB의 메모리안에 들어올 수 없는 방법입니다.

그렇기 때문에 구상한 방법은 큐의 크기를 n만큼 유지하는 것입니다.

1. 리스트 한 줄을 입력으로 받고 최소 힙에 모두 넣습니다.
2. 최소 힙의 크기가 n이 될 때 까지 pop해줍니다.
3. 리스트를 모두 확인할 때 까지 반복하면 큐에는 가장 큰 숫자 n개 만큼이 들어가게 됩니다.

예제를 그림으로 통해 보겠습니다.

N = 1

N = 2

N = 3

N = 4

N = 5

---

풀이 코드

import sys
import heapq

input = sys.stdin.readline
n = int(input())
pq = []
for _ in range(n):
    # 다음 리스트를 우선순위 큐에 넣는다.
    for x in list(map(int, input().split())):
        heapq.heappush(pq, x)
    # 큐의 길이가 n이 될때까지 최소힙 구조에서 pop
    while len(pq) != n:
        heapq.heappop(pq)
print(heapq.heappop(pq))

---