185. 1655(가운데를 말해요) - 파이썬

import heapq
import sys

input = sys.stdin.readline
N = int(input())

leftHeap = []
rightHeap = []
result = []
for i in range(N):
    x = int(input())

    if len(leftHeap) == len(rightHeap):
        heapq.heappush(leftHeap, -x)
    else:
        heapq.heappush(rightHeap, x)

    if rightHeap and rightHeap[0] < -leftHeap[0]:
        leftValue = heapq.heappop(leftHeap)
        rigthValue = heapq.heappop(rightHeap)

        heapq.heappush(leftHeap, -rigthValue)
        heapq.heappush(rightHeap, -leftValue)

    result.append(str(-leftHeap[0]))
print("\n".join(result))

문제요약

값이 들어올 때 마다 오름차순으로 했을 경우 중앙값을 구하라 (만약 짝수면 두개의 중앙값 중 작은거 출력)

설명

먼저 단순히 생각을 하면 아래의 순서로 진행될 것이다.

이를 구현하기 위해 정렬을 계속 이용한다면 시간초과가 발생할 것이다.

따라서 힙 큐(우선순위 큐)를 이용한다.

힙 큐는 트리형태 여서 아무생각 없이 중앙을 출력 한다면 오류가 발생한다.

예를들어 50 10 20 을 큐에 저장하면 큐는 10 50 20 형태를 갖추고 있다.

하지만 heappop (우선순위 큐에서는 get) 을 통해 세번 출력을 한다면 10 20 50 으로 정상적으로 오름차순의 형태를 나타낼 것이다.

 

그러면 어떻게 가운데를 푸느냐?? 두개의  힙 큐를 이용한다.

다음과 같이 준비하여 왼쪽 힙은 중앙 값보다 작은 값, 오른쪽 힙은 중앙 값보다 큰값을 넣는다.

 

(1) 1 입력

왼쪽은 내림차순으로 정렬해야한다. (중앙값이 0번째 인덱스로 오기 위해서)

그러면 -를 붙여 힙에 입력하면 된다.

 

왼쪽과 오른쪽의 길이가 같은 경우에는 왼쪽에 집어 넣는다.

 

(2) 5 입력

왼쪽 힙과 오른 쪽 힙의 길이가 같지 않을 경우에는 먼저 오른쪽 힙에 집어 넣는다.

그 후 왼쪽의 0번째 값과 오른쪽의 0번째 값을 비교한다 (이 둘이 짝수일 경우의 중앙 값)

※ 왼쪽 힙은 -를 붙여 주었기 때문에 -를 붙여 비교한다.

 

만약, 왼쪽값이 오른쪽 값보다 크다면 두개의 위치를 서로 바꿔준다.

 

(3) 2 입력

다시말하지만 왼쪽은 0번째 값이 가장 큰 값이 되어야 하므로 내림차순으로 정렬한다. (맨 위가 중앙값)

 

(1)번과 마찬가지로 길이가 같은 경우이기 때문에 왼쪽 힙에 값을 넣는다.

 

그 후, 오른쪽에 값이 있을 경우 (2)번의 과정을 진행한다. (왼쪽에 0번째 값과 오른쪽의 0번째 값을 비교하는 과정)

 

(4) 10 입력

이후는 똑같은 과정이므로 그림만 보여주도록 하겠다.

 

(5) -99 입력

(6) 7 입력

(7) 5 입력

이미 존재하는 5가 입력 되었다.

하지만 우리는 왼쪽과 오른쪽 힙의 길이를 통해서 값을 넣는 과정을 진행하기 때문에 크게 문제 되지 않는다.

 

위 과정과 똑같이 왼쪽, 오른쪽의 길이가 같으므로 우선  왼쪽 힙에 저장을 한다.(내림차순을 위해 -를 붙이고)

왼쪽의 0번째 5와 오른쪽 0번째 5를 비교했을 때 둘은 같기 때문에 자리이동은 필요 없으며 마지막 결과의 중앙값은 5가 된다.