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

https://www.acmicpc.net/problem/2075

 

코드

import heapq as hq
import sys
input = sys.stdin.readline

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

init_numbers = list(map(int, input().split()))
for num in init_numbers:
    hq.heappush(heap, num)

for i in range(n-1):
    numbers = list(map(int, input().split()))
    for num in numbers:
        if heap[0] < num:
            hq.heappush(heap, num)
            hq.heappop(heap)

print(heap[0])

 

접근 방식

1. 처음에 주어진 N개의 숫자를 최소 힙에 모두 넣는다

2. 이후 추가로 들어오는 숫자들을 확인하며, 힙의 최솟값(heap[0])보다 큰 경우에만 그 숫자를 힙에 넣고, 힙에서 최솟값을 제거 한다

3. 위 과정을 N-1번 반복하면, 힙에는 가장 큰 N개의 숫자만 남게 된다.

4. 최종적으로 힙의 최소값이 N번째로 큰 숫자가 된다

 

배운 점

1. 힙 자료구조를 이용하면 효율적으로 N번째 큰 수를 찾을 수 있다