백준, 중앙값 구하기, 2696

[유형]

자료구조

 

[문제링크]

https://www.acmicpc.net/problem/2696

 

[요약]

각 테스트 케이스에 대해 첫째 줄에 출력하는 중앙값의 개수를 출력하고, 둘째 줄에는 홀수 번째 수를 읽을 때 마다 구한 중앙값을 차례대로 공백으로 구분하여 출력한다. 이때, 한 줄에 10개씩 출력해야 한다.

 

[문제풀이]

먼저, 특정 N번째 원소까지의 중앙 값을 AkAk라고 가정한다면, 우리는 다음과 같이 이분화를 할 수 있게 된다.
A1 ... An = {Ak 보다 작은 원소들의 집합 } + { Ak 보다 크거나 같은 원소들의 집합 }

이 때, n이 홀수 일 때 유일한(unique) 중앙값이 하나가 정의가 되고 이 때 이것을 출력하고자 한다.

 

{ Ak 보다 작은 원소들의 집합 } 과 { Ak 보다 크거나 같은 원소들의 집합 } 은 최대 1이 차이나고, 항상 { Ak 보다 작은 원소들의 집합 }은 { Ak 보다 크거나 같은 원소들의 집합 } 보다 크거나 같다. 이렇게되면 { Ak 보다 작은 원소들의 집합 }의 루트 노드가 항상 중앙값임이 보장된다.

{ Ak 보다 작은 원소들의 집합 } 의 모든 원소들은  { Ak 보다 크거나 같은 원소들의 집합 } 의 모든 원소들 보다 작다.즉, { Ak 보다 작은 원소들의 집합 }의 최댓값이 { Ak 보다 크거나 같은 원소들의 집합 }의 최솟값 보다 작아야 한다는 것을 의미한다.

{ Ak보다 작은 원소들의 집합 }은 최댓값을 빠르게 구하기 위해 Max heap으로 구현을 하고

{ Ak 보다 크거나 같은 원소들의 집합 }은 최솟값을 빠르게 구하기 위해 Min heap으로 구현을 한다.

 

 

1. 중앙값을 기준으로, 중앙값보다 작거나 같으면 max_heap에, 중앙값보다 크면 min_heap에 추가한다.

2. max_heap의 길이가, min_heap의 길이보다 2이상 길다면, max_heap의 루트 노드 값을 min_heap으로 이동.

3. max_heap의 길이보다 min_heap의 길이가 더 길다면, 길이가 같아질 때까지 min_heap의 루트 노트 값을 max_heap으로 이동.

4. i가 짝수일때, max_heap의 루트 노드 값을 medians에 append.

import sys
def input():
    return sys.stdin.readline().rstrip()

import heapq

for _ in range(int(input())):
    M = int(input())
    num_list = list()
    for i in range((M-1) // 10 + 1) :
        num_list += list(map(int, input().split()))

    min_heap = []
    max_heap = [-num_list[0]]
    medians = [num_list[0]]

    for i in range(1,M):
        if -max_heap[0] < num_list[i]:
            heapq.heappush(min_heap, num_list[i])
        else:
            heapq.heappush(max_heap, -num_list[i])

        while len(max_heap) -len(min_heap) > 1:
            heapq.heappush(min_heap, -heapq.heappop(max_heap))
        while len(max_heap) -len(min_heap) < 0:
            heapq.heappush(max_heap, -heapq.heappop(min_heap))


        if not i%2 :
            medians.append(-max_heap[0])
            
    print(len(medians))

    for i in range(0, len(medians), 10):
        print(*medians[i:min(i + 10, len(medians))])

 

 

 

참고 https://kangminjun.tistory.com/entry/BOJ-2696번-중앙값-구하기 [알고리즘 문제풀이:티스토리]

https://magentino.tistory.com/346