파이썬) N번째 큰 수 - BOJ

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

2075번: N번째 큰 수

import heapq

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

for _ in range(n):
    a = list(map(int, input().split()))
    for num in a:
        # 배열 개수가 n개 미만이면
        if len(heap) < n:
            # 넣음
            heapq.heappush(heap, num)

        else:
                # 입력값이 heap의 최소값보다 크다면
            if heap[0] < num:
                # 최소값을 빼고 입력받은 숫자를 넣음
                heapq.heappop(heap)
                heapq.heappush(heap, num)

print(heap[0])

우선 이게 어떻게 돌아가는지 살펴보자.

n번째로 큰 수라하면 모든 값을 오름차순으로 정렬했을때 n번째의 숫자이다.

 

이를 우선순위 큐로 나타내자면 

배열에는 n개의 숫자까지만 들어간다. 때문에 최종으로 남은 배열의 요소들은 n가 되고 그 중 0번째(최소값)은 모든 숫자들 중 n번째로 큰 수가 된다.