우선순위 큐(유형정리) - 백준 2075

2075번: N번째 큰 수 (acmicpc.net)

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번째 큰 수를 출력한다.

예제 입력 1 복사

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

예제 출력 1 복사

35

 

처음 문제를 보자마자 떠오른 건 그냥 max_heap 구현으로 가장 max 한 값에서 찾으면 되는게 아닌가? 라는 생각이었다. 하지만, 문제를 풀면서 보니 그냥 min_heap에서 가장 앞의 index를 찾아내는 것이 가장 쉽다는 생각이 들어서 heapq 모듈을 그대로 구현하여 문제를 해결했다.

 

※ 알고리즘

1. 리스트에 숫자를 모두 집어넣는다.

2. Heap이 N보다 작다면 Heap에 num을 계속 push한다.

3. Heap이 N보다 작지 않은 경우에서 Heap의 제일 처음 index가 새로 입력된 num 보다 작다면 Heap에서 pop 해주고, 새로운 num을 다시 push 해준다.

 

import heapq as hp
N = int(input())

Heap = []
for i in range(N):
    num_list = list(map(int, input().split()))
    for num in num_list:
        if len(Heap) < N:
            hp.heappush(Heap, num)
        else:
            if Heap[0] < num:
                hp.heappop(Heap)
                hp.heappush(Heap, num)

print(Heap[0])

 

이렇게 하여 N번째의 최댓값을 구할 수 있다