[백준/python] 2075번 : N번째 큰 수

문제

N×N의 표에 수 N2개 채워져 있다. 채워진 수에는 한 가지 특징이 있는데, 모든 수는 자신의 한 칸 위에 있는 수보다 크다는 것이다. N=5일 때의 예를 보자.

12	7	9	15	5
13	8	11	19	6
21	10	26	31	16
48	14	28	35	25
52	20	32	41	49

이러한 표가 주어졌을 때, N번째 큰 수를 찾는 프로그램을 작성하시오. 표에 채워진 수는 모두 다르다.

입력

첫째 줄에 N(1 ≤ N ≤ 1,500)이 주어진다. 다음 N개의 줄에는 각 줄마다 N개의 수가 주어진다. 표에 적힌 수는 -10억보다 크거나 같고, 10억보다 작거나 같은 정수이다.

출력

첫째 줄에 N번째 큰 수를 출력한다.

코드

import heapq

N = int(input())
heap = []

for _ in range(N):
    row = list(map(int,input().split()))
    for num in row : 
        if len(heap) < N:
            heapq.heappush(heap, num)
        else:
            if num > heap[0] :
                heapq.heappop(heap)
                heapq.heappush(heap, num)

print(heap[0])

코드풀이

N번째 최댓값을 구하기 위하여 최소힙을 사용하였다.
힙을 N칸까지만 유지하여, N번째 후 부터는 힙의 최솟값과 새로 추가되는 값을 비교한다.
힙 내부의 최솟 값보다 큰 경우 힙의 최솟값을 pop하고 새 값을 push 한다.
연산을 완료한 후 힙의 최솟값을 출력한다.