[백준] 2075번 N번째 큰 수 (Heapq)

문제

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

 

---

 
우선순위 큐를 이용하는 문제로 Heapq를 이용하여 풀었다.

우선순위 큐(Priority Queue)는 FIFO 형태의 일반 큐(Queue)와 다르게 우선순위가 높은 값이 먼저 나오는 구조로 되어있다. 이 우선순위 큐는 힙(Heap)의 형태로 되어 있는데, 힙은 최소값과 최대값을 찾을 수 있는 완전이진트리 형태의 자료구조이다.

파이썬에도 priorityqueue와 heapq를 모두 사용할 수 있지만, 속도가 좀 더 빠른 heapq를 이용하도록 하자.

 

 

heapq는 최소힙의 형태로 되어있다. pop을 통해 데이터를 빼오면 제일 작은 수를 구할 수 있다.
새로 입력한 값이 heapq의 root 값보다 클 경우 heapq에 삽입한다. 이 과정을 반복하면 heapq에는 전체 수 중 큰 수 N개를 얻을 수 있다. N개씩 입력을 받고 있기 때문에 heapq의 크기는 항상 N으로 유지된다.

 

숫자를 이용해 위 풀이를 설명하면 아래와 같다.

heapq의 크기가 3(=N)이면, 3번째로 큰 수(=N번째로 큰 수)를 찾아야 한다.
3(=N)개씩 입력을 받아 비교하여 큰 수들을 heapq에 저장한다. heapq에는 3(=N)개의 제일 큰 수들이 저장되어 있다.
heapq는 기본 최소힙 형태로 heappop()을 하게 되면 전체 중 3(=N)번째로 큰 수를 찾을 수 있다.

 

import sys
import heapq

N = int(sys.stdin.readline())
heap_List = []

# 첫번째 줄 입력은 그대로 heapq에 추가
heap_List = list(map(int, input().split()))
heapq.heapify(heap_List)

# N번째 줄까지 크기를 비교하여 heapq에 추가
for i in range(N-1):
    n_list = list(map(int, input().split()))
    
    for n in n_list:
        if heap_List[0] < n:
            heapq.heappop(heap_List)
            heapq.heappush(heap_List, n)

# heapq에는 크기가 큰 수들이 들어가있음
# heapq는 최소힙 형태로 0번째 인덱스는 N개의 수 중 제일 작은 수이자 N^2개의 수 중 N번째로 큰 수
print(heap_List[0])
# print(heapq.heappop(heap_List))

 

#1.
다른 사람들의 코드를 보니 N개의 크기를 맞추기 위해 개수를 비교하였지만, 나는 개수를 비교하지 않았다.
이유는 위에서 풀이한 과정과 같다.

첫번째로 입력한 값들은 비교할 데이터가 없으니 그대로 추가한다. 
list 형태로 받은 heap_List를 heaqp.heapify() 를 통해 heapq의 형태로 만들어주었다.

 

#2.
N번째 줄까지 입력을 받아 수를 비교해준다. 첫번째 줄은 기본으로 heapq에 넣어주었으니 N-1만큼 반복하였다.
n_list 속 원소값을 하나씩 가져와 heapq의 '첫번째 요소=제일 작은 값'과 비교한다.

새로 입력 받은 값이 더 클 경우 heapq에 push하며, 새로운 데이터가 들어갈 때마다 최소힙 형태가 생성된다.

 

#3.
최소힙 형태로 되어있는 리스트의 첫번째 요소를 출력하거나, heapq.heappop()을 통해 제일 작은 요소를 출력한다.
이 모두 같은 결과를 볼 수 있다.