백준 1655번 (힙 자료구조와 heapq 모듈)

리스트를 만들고 요소가 들어올 때마다 정렬하고 중간값을 출력하는 알고리즘을 짜봤다.

잘 돌아가기는 했지만 돌아가는게 너무 오래걸려 오답이었다. 아무래도 출제자는 정렬로 푸는 것을 원하지 않는 모양이다.

 

빠르게 돌아가는 알고리즘을 만들기 위해서 힙을 사용했다.

 

힙이란 완전 이진 트리의 일종으로 최댓값이나 최솟값을 빠르게 찾아내기 위한 자료구조이다.

 

부모가 자식보다 큰 최대 힙과 부모가 자식보다 작은 최소 힙이 있다.

 

heapq 모듈은 이런 힙 자료구조를 파이썬에서 이용하게 해준다.

min heap을 이용하면 원소들은 항상 정렬된 상태로 삽입, 삭제되고 가장 작은 값은 언제나 인덱스 0에 위치한다.

그리고 그 뒤에 원소들은 왼쪽 자식 노드는 부모 노드*2, 오른쪽 자식 노드는 부모 노드*2 + 1로 계속 이어진다.

(루트노드 index=0 제외)

 

import heapq를 해주고

minheap = []

heappush(minheap, 4)

heappush(minheap, 1)

heappush(minheap, 7)

heappush(minheap, 3)

을 하고

print(minheap)을 하면

[1, 3, 7, 4]로 출력 되는데 이것은

이것처럼 정렬되어 있는 것을 의미한다.

 

heapq모듈은 최소 힙만 작동하기 때문에 최대 힙을 사용하려면 좀 요령이 필요하다.

 

heappush(maxheap, -num)처럼 하면

-num들을 비교해서 최소 힙 규칙대로 정렬되지만 우리는 다시 뽑아올 때 다시 마이너스를 붙이면서 뽑아오면 최대 힙처럼 사용할 수 있는 것이다.

 

 

그럼 이제 이 힙 자료구조를 어떻게 이 문제에 응용하느냐 하면.

 

우선 힙을 두 개 만든다. 하나는 leftheap이고 최대 힙이며 다른 하나는 rightheap이고 최소 힙이다.

leftheap의 첫 원소 (루트 노드)가 중간 값이다.

 

값이 들어오면 leftheap과 rightheap에 번갈아가면서 넣어주는데, 중간값보다 작은 값이 rightheap에 들어가면 두 힙의 첫 원소를 빼서 반대로 넣어준다. 반대로 중간값보다 큰 값이 leftheap에 들어가도 두 힙의 첫 원소를 빼서 반대로 넣어준다.