[2023 알고리즘 스터디] 4조 이은선 5주차 - 백준 2075

우선순위 큐를 이용한 정렬 문제

 

입력

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]번째 값이 이 문제의 출력값이 된다.

 

+) comment 

이렇게 우선순위 큐를 이용해 정렬을 하여 문제를 풀면 쉽게 풀 수 있는 문제였다. 어떤 방식으로 정렬을 할지 고안해내는게 이 문제의 관건이였던 것 같다. 나는 이 문제를 heap을 이용해 풀었지만, 다른 풀이법이 떠오른다면 추가로 풀어보고, 재업로드할 예정이다.