1655번 - 가운데를 말해요

출처: 백준 알고리즘

주소: www.acmicpc.net/problem/1655

1655번: 가운데를 말해요

1655번 - 가운데를 말해요

문제 요약:

 (1) N개의 숫자가 차례대로 입력

 (2) 1 ~ N개 들어온 숫자들의 중간값 출력

 

문제 해결:

 A. 중간값 설정

 B. 중간값보다 작은 경우, MaxHeap에 저장

 C. 중간값보다 크거나 같은 경우, MinHeap에 저장

 D. MaxHeap과 MinHeap의 크기의 차이를 1이하로 유지

 

미리 공부할 내용:

  => heap에 대해 공부하기 위해 아래 블로그 참조

trying-ce-student.tistory.com/14

11279번 - 최대 힙

 

알고리즘:

 

 Fig. 전체적인 그림

 

전체적인 그림

 A. 중간값 설정

    => 초기 중간값(mid_val)은 처음으로 입력받은 값(x)로 설정

 

 B. 중간값보다 작은 경우, MaxHeap에 저장

    - (중간값(mid_val) > 입력받은 값(x)) 이면

      => MaxHeap.InputX(x)을 통해 MaxHeap에 입력

 

 C. 중간값보다 크거나 같은 경우, MinHeap에 저장

    - (중간값(mid_val) <= 입력받은 값(x)) 이면

      => MinHeap.InputX(x)을 통해 MinHeap에 입력

 

 D. MaxHeap과 MinHeap의 크기의 차이를 1이하로 유지

    - MaxHeap과 MinHeap의 크기의 차이를 1이하로 유지하는 이유

      => N이 홀수이면 중간값을 기준으로 나눴을 경우, 양쪽의 크기가 같아 차이가 0이다.

      => 또한, N이 짝수이면 중간값으로 기준으로 나눴을 경우, 양쪽의 크기의 차이가 1이다.

      => 따라서, 두 Heap의 차이를 1이하로 유지해야한다.

 

    - MinHeap의 heap_size에서 MaxHeap의 heap_size를 뺀 값을 dif_heap에 저장

     (1) (dif_heap < 0) 이면 MaxHeap의 heap_size가 MinHeap의 heap_size보다 1이상 차이나는 경우이다.

       => 1. 중간값(mid_val)을 MinHeap에 대입

       => 2. 중간값(mid_val)을 MaxHeap의 최대값으로 설정하고 그 값을 MaxHeap에서 삭제

     (2) (dif_heap > 1) 이면 MinHeap의 heap_size가 MaxHeap의 heap_size보다 2이상 차이나는 경우이다.

       => 1. 중간값(mid_val)을 MaxHeap에 대입

       => 2. 중간값(mid_val)을 MinHeap의 최소값으로 설정하고 그 값을 MinHeap에서 삭제

 

    - 여기서 dif_heap이 0이거나 1을 따지지 않는 이유

        => dif_heap이 0인 경우, 양쪽의 밸런스가 맞는 경우이다.

        => dif_heap이 1인 경우는 N이 짝수이지만, 항상 (mid_val < MinHeap의 최소값)을 만족한다.

        (* 하지만, dif_heap이 -1인 경우도 N이 짝수이지만, 항상 (MaxHeap의 최대값 < mid_val)을 만족하기에

          중간값을 변경해줘야 한다.)

 

소스 코드:

#include <iostream>
 
#define MAX_HEAP_LEN 100001
 
/// <summary>
/// MaxHeap Class 생성
/// </summary>
 
class MaxHeap {
private:
    int heap[MAX_HEAP_LEN];
    int heap_size;
public:
    MaxHeap();
    void InputX(int x);
    int DeleteX();
    int MaxVal();
    int HeapSize();
    void PrintHeap();
};
 
MaxHeap::MaxHeap() {
    for (int i = 0; i < MAX_HEAP_LEN; i++) {
        heap[i] = 10001;
    }
    heap_size = 0;
}
 
void MaxHeap::InputX(int x) {
 
    int idx = ++(heap_size);
 
    while ((idx != 1) && (x > heap[idx / 2])) {
        heap[idx] = heap[idx / 2];
        idx /= 2;
    }
 
    heap[idx] = x;
 
}
 
int MaxHeap::DeleteX() {
    int child_idx, parent_idx;
    int last_val, del_val;
 
    del_val = heap[1];
    last_val = heap[(heap_size)--];
 
    child_idx = 2;
    parent_idx = 1;
 
    while (child_idx <= heap_size) {
        if ((child_idx < heap_size) && (heap[child_idx] < heap[child_idx + 1])) {
            child_idx++;
        }
        if (last_val >= heap[child_idx]) {
            break;
        }
        heap[parent_idx] = heap[child_idx];
        parent_idx = child_idx;
        child_idx *= 2;
    }
    heap[parent_idx] = last_val;
 
    return del_val;
}
 
int MaxHeap::MaxVal() {
    return heap[1];
}
 
void MaxHeap::PrintHeap() {
    printf("MaxHeap: ");
    for (int i = 1; i <= heap_size; i++) {
        printf("%d ", heap[i]);
    }
    printf("\b\n");
}
 
int MaxHeap::HeapSize() {
    return heap_size;
}
 
//////////////////////////////////////////////////////////////
 
/// <summary>
/// MinHeap Class 생성
/// </summary>
 
class MinHeap {
private:
    int heap[MAX_HEAP_LEN];
    int heap_size;
public:
    MinHeap();
    void InputX(int x);
    int DeleteX();
    int MinVal();
    int HeapSize();
    void PrintHeap();
};
 
MinHeap::MinHeap() {
    for (int i = 0; i < MAX_HEAP_LEN; i++) {
        heap[i] = 10001;
    }
    heap_size = 0;
}
 
void MinHeap::InputX(int x) {
    int idx = ++(heap_size);
 
    while ((idx != 1) && (x < heap[idx / 2])) {
        heap[idx] = heap[idx / 2];
        idx /= 2;
    }
 
    heap[idx] = x;
}
 
int MinHeap::MinVal() {
    return heap[1];
}
 
void MinHeap::PrintHeap() {
    printf("MinHeap: ");
    for (int i = 1; i <= heap_size; i++) {
        printf("%d ", heap[i]);
    }
    printf("\b\n");
}
 
int MinHeap::DeleteX() {
    int child_idx, parent_idx;
    int last_val, del_val;
 
    del_val = heap[1];
    last_val = heap[(heap_size)--];
 
    child_idx = 2;
    parent_idx = 1;
 
    while (child_idx <= heap_size) {
        if ((child_idx < heap_size) && (heap[child_idx] > heap[child_idx + 1])) {
            child_idx++;
        }
        if (last_val <= heap[child_idx]) {
            break;
        }
        heap[parent_idx] = heap[child_idx];
        parent_idx = child_idx;
        child_idx *= 2;
    }
    heap[parent_idx] = last_val;
 
    return del_val;
}
 
int MinHeap::HeapSize() {
    return heap_size;
}
 
//////////////////////////////////////////////////////////////
 
/// <summary>
/// main 함수 생성
/// </summary>
 
int main() {
 
    // 변수 선언
    int n, x, dif_heap, mid_val;
    MaxHeap max_heap;
    MinHeap min_heap;
 
    // 입력 및 계산
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &x);
        // 처음값을 중간값으로 설정
        if (i == 1) {
            mid_val = x;
        }
        // 처음값이 아닌 경우
        else {
            // 중간 값보다 작으면 max_heap에 삽입
            if (x < mid_val) {
                max_heap.InputX(x);
            }
            // 중간 값보다 크거나 같으면 min_heap에 삽입
            else {
                min_heap.InputX(x);
            }
            // min_heap과 max_heap의 heap_size의 차이 계산
            dif_heap = min_heap.HeapSize() - max_heap.HeapSize();
            // 1. dif_heap이 0인 경우는 같은 경우니까 양쪽의 밸런스가 맞는 경우다.
            // 2. dif_heap이 1인 경우는 짝수 개이지만 항상 (mid_val < min_heap의 최소값) 성립
            // 3. dif_heap이 -1인 경우에는 짝수 개이고 항상 (max_heap의 최대값 < mid_val) 성립하여 교환
            // max_heap의 heap_size가 더 큰 경우
            if (dif_heap < 0) {
                min_heap.InputX(mid_val);
                mid_val = max_heap.DeleteX();
            }
            // min_heap의 heap_size가 더 큰 경우
            if (dif_heap > 1) {
                max_heap.InputX(mid_val);
                mid_val = min_heap.DeleteX();
            }
        }
        printf("%d\n", mid_val);
    }
 
 
    return 0;
}

 

한줄평:

 -> 두가지 힙(heap)을 이용하여 중간값을 바로바로 구할 수 있다.