[백준-1655] 가운데를 말해요

문제

링크

풀이

import sys
import heapq
input = sys.stdin.readline

n = int(input())
leftarr = []
rightarr = []

for i in range(n) :
    x = int(input())
    if i % 2 == 0 :
        heapq.heappush(leftarr, -x)
    else :
        heapq.heappush(rightarr, x)
    try :
        left = -leftarr[0]
        right = rightarr[0]
        if -leftarr[0] > rightarr[0] :
            heapq.heappop(leftarr)
            heapq.heappop(rightarr)
            heapq.heappush(leftarr, -right)
            heapq.heappush(rightarr, left)
        print(-leftarr[0])
    except :
        print(-leftarr[0])

처음에는 단순하게 입력되는 수를 배열에 넣고, sort로 정렬한 후에 가운데 값을 출력하도록 했다.
역시나 시간 초과가 발생했다. 이 문제를 우선순위 큐를 이용해서 풀어야 하는데, 어떻게 해야 하는지 감이 오지 않았다. 그래서 결국 다른 분들의 코드를 참고했다.
다른 분들의 코드를 봤을 때 전혀 생각하지도 못한 방법이라 놀랐다.

먼저 우리는 가운데 수를 구해야 하므로 가운데를 기준으로 작은 쪽(왼쪽), 큰 쪽(오른쪽) 이렇게 두 개로 나눌 수 있다. 그러므로 배열을 두 개 생성한다.
입력값의 인덱스가 홀수인지, 짝수인지에 따라 왼쪽, 오른쪽 배열에 수를 집어 넣는다.
이때 배열은 힙을 통해 값을 집어 넣는다.
문제에서 외친 수의 개수가 짝수개라면 두 수 중에서 작은 수를 말해야 한다고 했으므로, 중간 수도 왼쪽 배열로 들어가야 한다. 그래서 수를 넣은 후, 왼쪽 배열에서 가장 큰 수를 출력하면 된다.
하지만, 오른쪽 배열(큰)에 들어간 수가 왼쪽 배열(작은)에서 가장 큰 수보다 작을 수도 있기 때문에 확인 후 두 수의 위치를 바꿔준다. 그 다음에 왼쪽 배열에서 가장 큰 수를 출력한다.

그리고 왼쪽 배열은 큰 수를 출력해야 하고 오른쪽 배열은 작은 수를 출력해야 하므로, 왼쪽 배열은 최대 힙, 오른쪽 배열은 최소 힙을 사용해야 한다. 그러므로 왼쪽 배열에 수를 넣고 뺄 때 -1을 곱해줘야 한다.

참고

• [백준] 1655 가운데를 말해요 파이썬 풀이