[백준/Python]2075_N번째 큰 수

문제

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

2075번: N번째 큰 수

풀이

우선순위 큐를 이용해서 풉니다.

먼저 입력으로 주어진 matrix의 첫 행을 최소 힙에 저장합니다.

힙의 root값(최솟값)은 n번째 큰 수가 되며 힙의 length를 유지하면서 반복문을 도는 게 핵심입니다.

이중 반복문을 돌면서 숫자 하나씩 힙에 heappush 하고 root값을 heappop 합니다.(단, 현재 힙의 root값보다 클 경우만 동작한다)

최종적으로 root값을 출력합니다.

코드

import heapq
import sys

n = int(sys.stdin.readline().rstrip())
numbers = []
lst = list(map(int, sys.stdin.readline().rstrip().split()))
for i in lst:
    heapq.heappush(numbers, i)
for _ in range(n - 1):
    lst = list(map(int, sys.stdin.readline().rstrip().split()))
    for num in lst:
        if num > numbers[0]:
            heapq.heappush(numbers, num)
            heapq.heappop(numbers)
print(numbers[0])