백준 1655번 - 가운데를 말해요

중간값을 찾는 문제이다. 매번 입력을 받을 때마다 지금까지 입력받은 수들의 중간값을 출력해주면 된다. 정렬을 한 뒤 중간 index의 값을 출력해주면 되겠지만, 입력 값이 100,000개이기 때문에, O(n^2)의 시간 복잡도를 생각하면 시간 초과가 뜰 것이다.

 

이번 단계가 우선순위 큐인 만큼 힙을 이용해야한다. 예를 들어 11개의 원소가 있고, 그 중 중간값의 특징을 생각해보자. 11개를 오름차순으로 정렬한다고 할 때 중간값을 포함한 왼쪽 6개중에서 중간값은 그들중에서 최댓값일 것이고, 오른쪽 5개의 원소들의 최솟값보다 작을 것이다. 짝수개일때도 마찬가지로, 만약 10개라고 가정한다면, 중간값을 포함한 왼쪽 5개중에서 최댓값이고, 오른쪽 5개의 원소들의 최솟값보다 작을 것이다.

 

꼭 정렬을 하여 최소 최대를 비교할 필요가 없기때문에, 입력을 받을 때 하나씩 최대힙과 최소힙에 넣어준다. 그러면 힙 자체에서 최댓값과 최솟값을 루트(heap[0])로 보내주고, 각 힙의 루트를 비교해서 작은 값을 출력해주면 된다.

조심해야할 점은 최대힙에는 위에서 든 예시에서 왼쪽 6개의 수들을, 최소힙에는 오른쪽 5개의 수들을 넣어줘야하기 때문에, 만약 최대힙의 루트가 최소힙의 루트보다 클 경우에는 루트값을 서로 교환해주어야 한다.

 

예를 들어, 3,7,5,6이 차례대로 입력되었다고 한다면, 3과 5는 최대힙에, 7과 6은 최소힙에 저장되었을 것이다. 그 뒤 9가 입력되었다고 하면, 원래대로면 9는 최대힙에 저장되지만, 그렇게되면 3,5,9가 왼쪽 3개가 되고 6,7이 오른쪽 2개가 될 것이다. 그러므로 현재의 루트값인 9와 6을 바꾸어주어서 중간값을 관리해주어야한다.

 

##함수 선언 부분
import sys
import heapq
##변수 선언 부분
max_heap = []
min_heap = []
num = 0
##메인 함수 부분
if __name__ == "__main__":
    N = int(sys.stdin.readline())
    for i in range(N):
        num = int(sys.stdin.readline())
        if i % 2 == 0: #차례대로 최대 힙과 최소 힙에 넣어준다.
            heapq.heappush(max_heap,-num)
        else:
            heapq.heappush(min_heap,num)
        if i == 0:
            print(-max_heap[0])
        else:
            if -max_heap[0] > min_heap[0]: #최대 힙의 최댓값이 최소 힙의 최솟값보다 크면 서로 교환해준다.
                max_num = -heapq.heappop(max_heap)
                min_num = heapq.heappop(min_heap)
                heapq.heappush(max_heap,-min_num)
                heapq.heappush(min_heap,max_num)
            print(min(min_heap[0],-max_heap[0]))

힙을 이용해서 풀어야하는 것은 알았지만, 중간값에 접근하는 방법을 생각해내는 것이 어려웠다. 중간을 기준으로 왼쪽의 최댓값과 오른쪽의 최솟값을 비교하여 중간값을 구할 수 있다는 것을 배웠다.