(파이썬) 백준 2075번 "N번째 큰 수"

---

# 접근법

 

우선순위 큐를 이용합니다.

 

최소 힙의 크기를 N으로 고정시켜가며 숫자들을 힙에 넣었다 뺐다 반복합니다.

 

최소 힙에서 요소를 제거할 때는 항상 최솟값이 제거되므로, 모든 수를 넣었다 빼기를 반복했을 때 최종적으로 힙에 남게 되는 수들은 N * N개의 숫자들 중 제일 큰 숫자 N개가 됩니다.

 

* 이 방법은 '모든 수는 자신의 한 칸 위에 있는 수보다 크다'라는 규칙을 딱히 이용하지 않고 풀 수 있는 풀이법입니다.

 

 

 

 

---

# 답

import heapq

h = []
n = int(input())

for _ in range(n):
    s = map(int, input().split())
    for i in s:
        if len(h) >= n:
            heapq.heappushpop(h, i)
        else:
            heapq.heappush(h, i)
            
print(h[0])