[백준][Python] 2075번 N번째 큰 수

2075번: N번째 큰 수

 

코드

import sys
import heapq
hq = []
N = int(input())
for _ in range(N):
    num = list(map(int,sys.stdin.readline().split()))
    if hq:
        for i in num:
            min = hq[0]
            if i > min:
                heapq.heappop(hq)
                heapq.heappush(hq,i)
    else:
        for i in num:
            heapq.heappush(hq,i)
print(hq[0])

 

설명

한 줄마다 N개의 숫자가 주어지고 구해야하는 값도 N번째로 큰 값이기 때문에 N개로만 이루어진 최소힙을 만들면 [0]번째 값이 N번째로 큰 값이 된다. 

첫 줄에서 입력받은 N개의 수는 일단 최소힙에 push를 해준다. 최소힙은 N개로만 이루어져야 하므로 힙이 비어있지 않을 때는 입력받은 값과 현재 최소힙에서의 최솟값(min)을 비교하여 만약 min보다 입력 값이 더 크면 min을 pop해주고 입력값을 push 해준다. 이것을 계속 반복하다 보면 마지막에는 N*N개의 숫자중 가장 큰 N개의 숫자만 남게 된다. 따라서 최소힙의 [0]번째 값을 출력해주면 된다.