[ 백준 1655 ] 가운데를 말해요 (C++)

백준의 가운데를 말해요(1655) 문제이다.

[ 문제 바로가기 ]

[ 문제풀이 ]

접근 방법을 잘 모르겠어서 다른 분들의 생각을 조금 참고해서 해결한 문제이다.

먼저 2개의 힙을 사용해서 문제를 해결할 수 있다. 하나는 '최댓값이 가장 top에 위치하게 되는 최대힙', 또 하나는 '최소값이 가장 top에 위치하게 되는 최소힙'. 이 2개의 힙으로 값을 삽입하는 그 순간 순간의 중간값을 찾을 수가 있다.

2개의 힙을 이용해서 구현할 것인데, 2개의 규칙에 맞게 삽입을 해 주어야 한다.

1. 최대힙의 크기는 항상 최소힙의 크기보다 같거나 '1'만큼 더 크다.

2. 최소힙의 모든 원소는 최대힙의 모든 원소보다 항상 크거나 같아야 한다.

    즉, 최소힙의 가장 top() 값은 항상 최대힙의 가장 top() 값 보다 크거나 같아야 한다.

바로 이 2가지 규칙이다. 위의 규칙에 맞게 힙에 데이터를 삽입하는 과정을 보기 전에, 아직 힙에 대해서 잘 모른다면 아래의 글을 읽고 오도록 하자.

[ 자료구조 Heap 알아보기 (Click) ]

가장 초기의 최대힙과 최소힙의 상태는 { } 일 것이다. 아무런 데이터가 존재하지 않는다.

여기에다가 문제의 예시로 나온 { 1, 5, 2, 10, -99, 7, 5 } 를 삽입하는 과정을 통해 그 과정을 알아보자. 위의 규칙을 반드시 지키면서 진행해야 한다.

첫 번째 데이터 = 1.

현재, 최대힙의 크기(0) = 최소힙의 크기(0) 이기 때문에, 이 상태에서 최소힙에 '1'을 삽입해준다면, 최소힙의 크기가 최대힙의 크기가 더 커져버리게 되므로 규칙1에 어긋나게 된다. 따라서, 이 경우에는 '최대힙'에 '1'을 삽입해주자.

★ 최대힙 = { 1 } , 최소힙 = { }

(찐하게 표시된 글씨는 해당 힙에서 가장 top()에 있는 값을 의미합니다.)

두 번째 데이터 = 5

현재, 최대힙의 크기는 1이고, 최소힙의 크기는 0이기 때문에, 이 경우에 최대힙에 '5'를 삽입해준다면, 최대힙의 크기가 최소힙의 크기보다 '2'만큼 더 커져버리기 때문에, 규칙1에 어긋나게 된다. 따라서, 이 경우에는 '최소힙'에 '5'를 삽입해주자.

최소힙에 '5'를 삽입하더라도, 2번규칙 또한 어긋나지 않기 때문에 그대로 삽입해주자.

★ 최대힙 = { 1 } , 최소힙 = { 5 }

세 번째 데이터 = 2

현재, 최대힙의 크기(1) = 최소힙의 크기(1) 이므로, 규칙1을 위반하지 않기 위해서, 최대힙에 '2'를 삽입해주자.

★ 최대힙 = { 2 , 1 } , 최소힙 = { 5 }

네 번째 데이터 = 10

규칙1을 위반하지 않기 위해서, 최소힙에 삽입을 해주자. 최소힙에 '10'을 삽입하더라도, 규칙2 또한 어긋나지 않게 된다.

★ 최대힙 = { 2 , 1 } , 최소힙 = { 5 , 10 }

다섯번째 데이터 = -99

규칙1을 위반하지 않기 위해서, 최대힙에 삽입을 해주자.

★ 최대힙 = { 2 , 1 , -99 } , 최소힙 = { 5 , 10 }

여섯번째 데이터 = 7

규칙1을 위반하지 않기 위해서, 최소힙에 삽입을 해주자. 삽입하더라도 규칙2 또한 어긋나지지 않는다.

★ 최대힙 = { 2 , 1 , -99 } , 최소힙 = { 5 , 7 , 10 }

마지막 데이터 = 5

규칙1을 위반하지 않기 위해서, 최대힙에 삽입을 해주자.

★ 최대힙 = { 5 , 2 , 1 , -99 } , 최소힙 = { 5 , 7 , 10 }

삽입하더라도, 최대힙의 top()값인 '5'는 최소힙의 top()값인 '5'보다 작거나 같기 때문에 규칙2에도 어긋나지 않는다.

이렇게 모든 데이터를 삽입해보았다.

그런데 중간값은 어떻게 찾을까 ???

본인이 위에 과정을 진행하면서, 데이터를 규칙에 맞게 하나씩 넣을 때 마다, 최대힙과 최소힙의 상태를 표현했었다.

눈에 띄게 표현하기 위해서 앞에 '★' 를 달아놓았다. 이 때, 최대힙의 top() 값들을 한번 보자.

최대힙의 top()값들을 순서대로 출력하면 그게 중간값이다.

위의 예시에는 규칙2를 위반하는 경우가 없는데 위반할 경우에는, 최대힙의 top()값과 최소힙의 top()값을 swap해주면 된다.

예를 들어서 { 1 , -1 } 을 삽입하는 경우를 보자.

중간값을 출력하라면 답은 1 , -1을 순차적으로 출력해야 한다.

먼저 최대힙에 '1'을 담는다. 그 후, 최소힙에 '-1'을 삽입한다. 그런데, 이는 규칙2를 위반하게 된다. 따라서 최대힙과 최소힙의 top()값들을 서로 바꿔주게 되면, 최대힙 = { -1 } 이 되고, 최소힙은 { 1 } 이 된다. 마찬가지로, 현재 상태에서의 최대힙의 top()값을 출력하게 되면 그 값이 중간값이 된다.

소스코드는 2개의 코드를 첨부하겠다. 하나는 Priority_Queue를 이용한 방법과, 또 한 가지는 Heap을 직접 구현해서 해결한 코드이다.

[ Priority_Queue Ver 소스코드 ]

#include<iostream>
#include<queue>
 
#define endl "\n"
#define MAX 100010
using namespace std;
 
int N;
int Arr[MAX];
 
void Input()
{
    cin >> N;
    for (int i = 0; i < N; i++) cin >> Arr[i];
}
 
void Solution()
{
    priority_queue<int> Max_PQ, Min_PQ;
    for (int i = 0; i < N; i++)
    {
        if (Max_PQ.size() > Min_PQ.size()) Min_PQ.push(-Arr[i]);
        else Max_PQ.push(Arr[i]);
        
        if (Max_PQ.empty() == false && Min_PQ.empty() == false)
        {
            if (Max_PQ.top() > -Min_PQ.top())
            {
                int Max_Value = Max_PQ.top();
                int Min_Value = -Min_PQ.top();
 
                Max_PQ.pop(); Min_PQ.pop();
                
                Max_PQ.push(Min_Value);
                Min_PQ.push(-Max_Value);
            }
        }
        cout << Max_PQ.top() << endl;
    }
}
 
void Solve()
{
    Input();
    Solution();
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}

[ Heap 직접구현 Ver 소스코드 ]

#include<iostream>
#include<algorithm>
 
#define endl "\n"
#define MAX 100010
using namespace std;
 
int N, Max_Heap_Idx, Min_Heap_Idx;
int Arr[MAX];
int Max_Heap[MAX];
int Min_Heap[MAX];
 
void Heap_push(int data, bool T)
{
    if (T == true)
    {
        int Idx = ++Max_Heap_Idx;
        Max_Heap[Idx] = data;
        while ((Idx != 1) && (data > Max_Heap[Idx / 2]))
        {
            swap(Max_Heap[Idx], Max_Heap[Idx / 2]);
            Idx = Idx / 2;
        }
    }
    else
    {
        int Idx = ++Min_Heap_Idx;
        Min_Heap[Idx] = data;
        while ((Idx != 1) && (data < Min_Heap[Idx / 2]))
        {
            swap(Min_Heap[Idx], Min_Heap[Idx / 2]);
            Idx = Idx / 2;
        }
    }
}
 
int Heap_pop(bool T)
{
    if (T == true)
    {
        int Result = Max_Heap[1];
        Max_Heap[1] = Max_Heap[Max_Heap_Idx--];
 
        int Parent = 1;
        int Child;
        while (1)
        {
            Child = Parent * 2;
            if (Child + 1 <= Max_Heap_Idx && Max_Heap[Child] < Max_Heap[Child + 1]) Child++;
            if (Child > Max_Heap_Idx || Max_Heap[Child] < Max_Heap[Parent]) break;
            swap(Max_Heap[Child], Max_Heap[Parent]);
            Parent = Child;
        }
        return Result;
    }
 
    int Result = Min_Heap[1];
    Min_Heap[1] = Min_Heap[Min_Heap_Idx--];
 
    int Parent = 1;
    int Child;
    while (1)
    {
        Child = Parent * 2;
        if (Child + 1 <= Min_Heap_Idx && Min_Heap[Child] > Min_Heap[Child + 1]) Child++;
        if (Child > Min_Heap_Idx || Min_Heap[Child] > Min_Heap[Parent]) break;
        swap(Min_Heap[Child], Min_Heap[Parent]);
        Parent = Child;
    }
    return Result;
}
 
int Get_Size(bool T)
{
    if (T == true) return Max_Heap_Idx;
    return Min_Heap_Idx;
}
 
int Top(bool T)
{
    if (T == true) return Max_Heap[1];
    return Min_Heap[1];
}
 
void Input()
{
    cin >> N;
    for (int i = 0; i < N; i++) cin >> Arr[i];
}
 
bool Empty(bool T)
{
    if (T == true)
    {
        if (Max_Heap_Idx == 0) return true;
        return false;
    }
    
    if (Min_Heap_Idx == 0) return true;
    return false;
}
 
void Solution()
{
    for (int i = 0; i < N; i++)
    {
        int Max_Heap_Size = Get_Size(true);
        int Min_Heap_Size = Get_Size(false);
        
        if (Max_Heap_Size > Min_Heap_Size) Heap_push(Arr[i], false);
        else Heap_push(Arr[i], true);
 
        if (Empty(true) == false && Empty(false) == false)
        {
            if (Top(true) > Top(false))
            {
                int Max_Value = Heap_pop(true);
                int Min_Value = Heap_pop(false);
                
                Heap_push(Min_Value, true);
                Heap_push(Max_Value, false);
            }
        }
 
        cout << Top(true) << endl;
    }
}
 
void Solve()
{
    Input();
    Solution();
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}