[Baekjoon, Python] 1655번 : 가운데를 말해요

도입

백준 단계별 풀기에서 우선순위큐 네 번째, 마지막 문제이다.

백준 1655번 문제, 입력, 출력

---

백준 1655번 입출력 예제 1

---

풀이

0. 우선순위큐는 큐의 FIFO의 구조가 아닌, 들어간 순서에 상관없이 우선순위가 높은 순서대로 OUT한다. 여기서, 최소힙이란, 루트노드에 가장 작은 값이 위치하는 것이다. 부모 노드는 항상 자식 노드에 들어있는 값 보다 작다.

 

1. 우선순위큐에 대한 자료구조에 대한 지식이 필요하다. 만약 우선순위큐 자료구조에 대한 지식이 아직 없다면, 먼저 해당 지식을 먼저 알아보자. 필자는 파이썬에서 제공하는 heapq를 활용하여 문제를 풀 예정이다. 자바의 PriorityQueue 클래스와 결을 같이 한다. heapq는 말그대로 힙의 자료구조를 활용하여 우선순위큐를 구현하는 것인데, 힙을 사용하는 이유, 즉 배열과 연결리스트를 사용하지 않는 이유는 시간복잡도에서 우선순위큐를 구현하는데 효율의 차이가 있기 때문이다. 자세한 사항은 자료구조 우선순위큐를 찾아보도록 하자.

 

2.1. heapq 라이브러리 내 함수

  - heappush(heap, item)

  - heappop(heap)

  - heapreplace(heap, item)

  - heappushpop(heap, item)

  - heapify(x)

2.2. heapq 라이브러리 내 함수 (Maxheap 버전)

  - _heappop_max(heap)

  - _heapreplace_max(heap, item)

  - _heapify_max(x)

 

3.0. heappush를 할 때, 튜플로 힙에 넣을 수 있다. 아래 그림은 python.org 출처의 heappush 사용법 예시이다. 튜플의 왼쪽은 비교 대상이 되고, 오른쪽은 실제 값으로 설정을 해서 넣을 수 있다. 

3.1. 이번 문제에서는 두개의 우선순위 힙을 사용할 것이다. 이전에 사용했던 최소힙 하나와 최대힙 하나씩을 사용한다. 전체  left는 최대힙(max heap), right는 최소힙(min heap)으로 하는데, 파이썬에서 제공하는 heapq의 경우 기본설정으로 최소힙을 가진다. 따라서, 최대힙은 조금 다르게 사용해줘야한다. 최대힙의 경우는 튜플의 첫번째에 -를 붙여서 음수로 만들어서 사용한다. 조금 더 알아보자면, 튜플 첫번째는 우선순위를 비교하는 값이 되는데, 음수를 포함해 가장 작은수를 최고 우선순위로 가지기 때문이다.

 

3.2. 다음 그림을 보면 이해가 쉬울 것이다. 왜 left와 right으로 변수를 썻을까? left+right = heapq total로 볼 수 있다. heapq total 을 보면 정수를 넣을 때마다 만들어지는 전체 배열이다. 저기서 중간값을 보면 1, 1, 2, 2, 2, ... 이런식인 것을 확인할 수 있다. left의 첫번째와 right의 첫번째를 비교해서 만약에 left가 더 크다면, 두개의 값을 바꿔준다. 그래야 우선순위로 정렬된 heapq total을 만들 수 있기 때문이다.

---

코드

import heapq
from sys import stdin

left, right = [],[]
n = int(stdin.readline())

for _ in range(n):
    num = int(stdin.readline())     # 수빈이가 정수를 하나씩 외칠때마다 수빈이가 말한 수 중에서 중간값을 말해야 한다.
    if len(left) == len(right):     # (홀수)중간값 말하기
        heapq.heappush(left,(-num,num))     #left(최대힙)에 정수를 넣는다. 배열 젤 앞에 최댓값이 들어감.
    else:                           # (짝수)중간에 있는 두수 중 작은 수 말하기
        heapq.heappush(right, (num,num))    #right(최소힙)에 정수를 넣는다. 배열 젤 앞에 최솟값이 들어감.

    if right and left[0][1] > right[0][1]:
        var_left = heapq.heappop(left)[1]
        var_right = heapq.heappop(right)[1]
        heapq.heappush(right, (var_left, var_left)) #left max와 right min 비교, left max >? right min과 교체
        heapq.heappush(left, (-var_right, var_right))

    print(left[0][1])

---

마무리

우선순위큐 4문제중 마지막 문제로, left right 두개의 배열을 사용하는 것이 신기했다! 충분히 새로운 접근이였던 것 같다. 키로거 문제와 비슷한 듯하다.