[BOJ/백준] 1655 가운데로 말해요

import heapq
import sys
N = int(input())


max_heapq = []
min_heapq = []
for _ in range(N):
    number = int(sys.stdin.readline())
    if len(max_heapq) == len(min_heapq):
        heapq.heappush(max_heapq,-number)
    else:
        heapq.heappush(min_heapq,number)
    if min_heapq and max_heapq and min_heapq[0] < -max_heapq[0]:
        max_number = -heapq.heappop(max_heapq)
        min_number = heapq.heappop(min_heapq)

        heapq.heappush(max_heapq,-min_number)
        heapq.heappush(min_heapq,max_number)
    print(-max_heapq[0])

우선순위 힙을 사용하는 기본적인 문제인 것 같다.

 

과거에도 다익스트라 알고리즘 문제를 풀때 우선순위힙큐를 사용했지만, 여전히 우선순위 힙을 사용하는데, 어려움을 겪었던 문제다.

 

문제 자체의 기본적인 생각은 다음과 같다. 

 

가운데 값을 기준으로 가운데 값보다 큰 경우는 무조건 우측에 두는 것이다.  그리고 작은 값은 좌측에 두는 것이다.

 

그러므로, min_heapq는 가운데 값을 기준으로 우측에 있는 값이고, max_heapq는 가운데 값을 기준으로 좌측에 있는 값이다.

 

문제 조건 중 가운데 값을 출력하고, 짝수일경우 가운데 값 2개 중 작은 값을 출력을 해야한다. 그러므로, max_heapq가 min_heapq보다 크기가 커야한다. 그래서 max_heapq와 min_heapq가 같은 크기이면, max_heapq에 먼저 넣어주고, 아닐 경우 min_heapq를 넣어줘야한다.

 

그리고 heapq는 무조건 최소값을 pop해주는 특징이 있으므로, max_heapq를 저장할때에는 가장 큰 값이 가장 먼저 나올수 있도록 -를 곱해줘야한다.

 

순서에 따라 맞춰서 max_heapq와 min_heapq에 순차적으로 넣어줘야한다. 하지만, 들어오는 입력값에 따라 가끔씩 min_heapq의 첫번째값이 max_heapq의 첫번째값보다 작은 경우가 생길수가 있다. 그럴 경우 두개를 바꿔주는 과정이 필요하다.

 

무조건 max_heapq의 첫번째 값이 전체의 가운데값이 되기위한 조치이다.

 

그리고 난뒤에, max_heapq의 첫번째 값을 출력해주면 된다.

 

heapq라는 라이브러리를 사용하면, 그리 어렵지 않은 문제이다. 하지만 나는 아직 트리와 우선순위힙에 대해서 잘 모르므로, 나중에 트리와 우선순위힙에 대해 더 자세히 공부하고, 라이브러리가 아닌 직접 구현으로 풀 수 있도록 연습해야겠다.