[Baekjoon] 정렬 - 2075 N번째 큰 수

문제

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

 

 

풀이

우선 순위 큐 사용

1) 주어진 숫자를 구하고자하는 길이 만큼 넣는다.

2) 제일 작은 수보다 큰 숫자가 주어진 경우 제일 작은 수를 제외하고 큰 숫자를 넣는다.

 

예시

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

 

첫번째 줄

5, 7, 9, 12, 15

 

두번째 줄

13인 경우: 5, 7, 9, 12, 15 → 5제외 13추가 → 7, 9, 12, 13, 15

8인 경우: 7, 9, 12, 13, 15 → 7제외 8추가 → 8, 9, 12, 13, 15

11인 경우: 8, 9, 12, 13, 15 → 8제외 11추가 → 9, 11, 12, 13, 15

19인 경우: 9, 11, 12, 13, 15 → 9제외 19추가 → 11, 12, 13, 15, 19

6인 경우: 패스

 

...

 

코드

import sys
import heapq

n = int(sys.stdin.readline().rstrip())
queue = []

for _ in range(n):
    numbers = list(map(int, sys.stdin.readline().rstrip().split()))
    for number in numbers:
        if len(queue) < n:
            heapq.heappush(queue, number)
        else:
            if queue[0] < number:
                heapq.heappop(queue)
                heapq.heappush(queue, number)

print(queue[0])