[C/C++] 백준 #2696 중앙값 구하기(힙)

힙(heap) 자료구조는 알고리즘에서 다양한 곳에서 사용할 수 있습니다.  우선순위큐가 대표적이고, 이 문제와 같이 중앙값을 찾는 용도로도 사용할 수 있습니다.  검색, 삽입, 삭제가 모두 \(O(\log N)\) 의 시간 복잡도를 가지므로, 큰 N에 대해서도 매우 빠르게 검색, 삽입, 삭제를 할 수 있습니다.

 

finding median values

 

아래는 문제의 링크입니다.

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

 

주요 포인트는 다음과 같습니다.

 

1. 입력과 출력 관리

• scanf를 사용하여 입력을 받고, printf와 putchar를 사용하여 출력을 합니다.

• 여러 테스트 케이스를 지원합니다.

2. 힙(heap)을 이용한 중간값 찾기

• 최대 힙(max-heap)과 최소 힙(min-heap)을 사용하여 중간값을 효율적으로 관리합니다.

• 최대 힙에는 중간값보다 작거나 같은 값이 저장되고, 최소 힙에는 중간값보다 큰 값이 저장됩니다.

3. 힙을 관리하는 논리

• 최대 힙의 크기와 최소 힙의 크기를 비교하여 균형을 맞춥니다.

• 중간값을 출력할 때는 최대 힙의 루트 값을 사용합니다.

 

#include <stdio.h>
#include <algorithm>

// 내림차순 정렬을 위한 비교 함수
bool cmp(int a, int b) { return a > b; }

int main()
{
    int t, n, s;
    scanf("%d", &t); // 테스트 케이스 수 입력
    while(t--)
    {
        int a[10000], b[10000], ac = 0, bc = 0; // 최대 힙 a와 최소 힙 b 및 힙의 크기 ac와 bc 초기화
        scanf("%d", &n); // 각 테스트 케이스의 정수 개수 입력
        printf("%d\n", (n + 1) / 2); // 중간값의 개수 출력
        
        for(int i = 1; i <= n; i++)
        {
            scanf("%d", &s); // 정수 입력
            if(ac == 0 || a[0] >= s) { // 최대 힙에 삽입 조건 확인
                a[ac++] = s; 
                std::push_heap(a, a + ac); // 최대 힙 유지
            }
            else { // 최소 힙에 삽입 조건 확인
                b[bc++] = s;
                std::push_heap(b, b + bc, cmp); // 최소 힙 유지
            }

            // 최대 힙의 크기가 최소 힙의 크기보다 2 이상 클 경우 균형 맞춤
            if(ac > bc + 1) 
            {
                std::pop_heap(a, a + ac); 
                b[bc++] = a[--ac]; 
                std::push_heap(b, b + bc, cmp); 
            }

            // 최소 힙의 크기가 최대 힙의 크기보다 클 경우 균형 맞춤
            if(ac < bc) 
            {
                std::pop_heap(b, b + bc, cmp); 
                a[ac++] = b[--bc]; 
                std::push_heap(a, a + ac); 
            }

            // 홀수 번째 수일 때 중간값 출력
            if(i & 1) { 
                printf("%d", a[0]); 
                putchar((i % 20) == 19 ? '\n' : ' '); // 20번째 수마다 줄바꿈
            }
        }
        if(n % 20 < 19) putchar('\n'); // 마지막 출력 후 줄바꿈
    }
    return 0;
}

 

동작 원리

 

1. 입력받기: 테스트 케이스 수와 각 테스트 케이스의 정수들을 입력받습니다.

2. 최대 힙과 최소 힙 사용: 정수를 최대 힙과 최소 힙에 적절히 분배하여 중간값을 유지합니다.

3. 균형 유지: 두 힙의 크기를 비교하여 필요시 힙을 조정합니다.

4. 중간값 출력: 현재 입력된 정수의 개수가 홀수일 때마다 최대 힙의 루트 값을 출력합니다.

5. 줄바꿈 처리: 20개의 수마다 줄바꿈을 합니다.