우선순위 큐 문제
입력
5
12 7 9 15 5 -> 15 12 9 7 5
13 8 11 19 6 -> 19 13 11 8 6
21 10 26 31 16 -> 31 26 21 16 10
48 14 28 35 25 -> 48 35 28 25 14
52 20 32 41 49 -> 52 49 41 32 20다음과 같은 5X5 입력이 주어졌을 때, 5번째로 큰 수를 찾기 위해서 일단 입력 받은 줄별로 내림차순 정렬을 진행해보았다. 하지만, 5번째로 큰 수를 찾기 위해선 맨 마지막 줄에 있는 수들끼리만 비교하면 될게 아니라 필요에 따라선 그 위에 줄의 숫자도 함께 비교하며 N번째로 큰 수를 찾아나가야 한다. 그렇다고 해서 세로 방향으로는 정렬된 상태로 입력 받은 수들을 몽땅 하나의 리스트에 넣고 재정렬시키는 방법은 비효율적인 방법이라고 생각했다. 따라서, 문제해결법으로 우선순위 큐 자료구조를 생각해냈다.
우선순위 큐(Priority Queue)이란?
큐나 스택과 비슷한 자료형이지만, 각 원소들은 우선순위를 가지고 있다. 우선순위 큐에서, 높은 우선순위를 가진 원소는 낮은 우선순위를 가진 원소보다 먼저 처리된다. 같은 우선순위를 가진다면, 먼저 들어온 원소를 처리한다.
우선순위 큐는 힙(heap)이라는 자료 구조를 통해 구현할 수 있다.
힙(Heap) 이란?
: 최댓값과 최솟값을 빠르게 찾기 위해 고안된 자료구조
- 각 노드의 key값이 해당 노드의 자식노드의 key값보다 작지 않거나 크지 않은 완전 이진트리
- 키 값의 대소관계는 부모-자식 노드 사이 간에만 성립하며 형제 노드 사이에는 영향을 미치지 않음
- 자식노드의 최대 개수는 힙의 종류에 따라 다르지만 이진트리에서는 최대 2개 (완전이진트리를 사용한다고 가정하자.)
- i번째 노드의 자식노드가 2개인데 왼쪽 자식노드는 2i, 오른쪽 자식노드는 2i+1이고, 부모노드는 i/2가 된다.
* 최대 힙 (max heap)
: 각 노드의 키 값이 그 자식노드의 키 값보다 작지 않은 힙
key(T.parent(v)) > key(v)
* 최소 힙 (min heap)
: 각 노드의 키 값이 그 자식노드의 키 값보다 크지 않은 힙
key(T.parent(v)) < key(v)
(1) 우선순위 큐(heap)을 이용한 풀이법 (성공)
import heapq
import sys
n = int(sys.stdin.readline())
q = []
for i in range(n):
l = list(map(int, input().split()))
if not q:
for num in l:
heapq.heappush(q, num)
else:
for num in l:
if q[0] < num:
heapq.heappush(q, num)
heapq.heappop(q)
한 줄마다 N개의 숫자가 주어지고 구해야 하는 값도 항상 N번째로 큰 값이기 때문에 N개로만 이루어진 최소힙을 만들어준다. 그렇게 되면, 최소힙의 0번째 값이 N번째로 큰 값이 된다. 첫 줄에서 입력받은 N개의 수는 일단 최소힙에 push를 해준다. 또, 최소힙은 N개로만 이루어져야 하므로 입력받은 값과 현재 최소힙에서의 최솟값(heap[0])을 비교하여 만약 heap[0]보다 입력 값이 더 크면 기존의 heap[0]을 pop해주고 입력값을 push 해준다. 이 과정을 줄단위로 계속 반복하다 보면 마지막에는 N*N개의 숫자중 가장 큰 N개의 숫자들만 남게 된다. 따라서 최소힙의 heap[0]번째 값이 이 문제의 출력값이 된다.