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

문제설명

---

입출력 예제

---

개념

　이 문제는 각 숫자를 입력받을 때마다 중간값을 계산하고 출력하는 것이다. 단순하게 배열에 값을 추가하고, 매 반복마다 중앙값을 출력하려면 시간 복잡도가 O(N^2)이 되어 시간 초과가 발생할 수 있다. 이를 해결하기 위한 최적화된 알고리즘이 두 힙 알고리즘이다.

　두 힙 알고리즘은 최대 힙과 최소 힙을 이용한다. 이 방식에서는 현재까지 입력받은 수 중 중간값 이하의 수를 최대 힙에, 중간값 초과의 수를 최소 힙에 저장한다. 따라서 중간값은 항상 최대 힙의 루트에 위치하게 된다. 이 알고리즘의 각 연산은 로그 시간 복잡도를 가지므로, 전체 시간 복잡도는 입력의 개수에 비례하는 선형 로그 시간 복잡도 O(N logN)를 가지게 된다. 이렇게 해서 큰 입력에 대해서도 효율적으로 문제를 해결할 수 있다.

---

풀이

#include <iostream>
#include <queue>
using namespace std;

int main()
{
    int N, n;
    cin >> N;

    priority_queue<int> maxHeap; 
    priority_queue<int, vector<int>, greater<int>> minHeap;

　최대힙 maxHeap과 최소힙 minHeap을 초기화해 준다.

    while (N--)
    {
        cin >> n;

        if (maxHeap.size() == minHeap.size())
            maxHeap.push(n);

        else
            minHeap.push(n);

　새로운 수를 입력받을 때, 두 힙의 크기가 같다면 최대 힙에 값을 추가하고, 다르다면 최소 힙에 값을 추가한다. 이는 중간값을 항상 접근 가능한 상태로 유지하려는 것인데, 이 두 힙은 각각 중간값을 기준으로 작은 값들과 큰 값을 저장하기 때문이다. 즉, 최대 힙의 루트는 중간값 이하의 값들 중 가장 큰 값이며, 최소 힙의 루트는 중간값 초과의 값들 중 가장 작은 값을 유지하려는 것이다. 

 

        if (!maxHeap.empty() && !minHeap.empty() && maxHeap.top() > minHeap.top())
        {
            int tmp1 = maxHeap.top(); maxHeap.pop();
            int tmp2 = minHeap.top(); minHeap.pop();
            maxHeap.push(tmp2);
            minHeap.push(tmp1);
        }

        cout << maxHeap.top() << "\n";
    }
}

　두 힙의 루트 노드의 값을 비교하여, 최대 힙의 루트 값이 최소 힙의 루트 값보다 크다면 이를 바꾼다. 이는 새로운 원소를 힙에 추가하는 과정에서 최대 힙의 원소가 최소 힙의 원소보다 작거나 같도록 유지하기 위함이다.

 

총합본

#include <iostream>
#include <queue>
using namespace std;

int main()
{
    int N, n;
    cin >> N;

    priority_queue<int> maxHeap; 
    priority_queue<int, vector<int>, greater<int>> minHeap; 

    while (N--)
    {
        cin >> n;

        if (maxHeap.size() == minHeap.size())
            maxHeap.push(n);

        else
            minHeap.push(n);

        if (!maxHeap.empty() && !minHeap.empty() && maxHeap.top() > minHeap.top())
        {
            int tmp1 = maxHeap.top(); maxHeap.pop();
            int tmp2 = minHeap.top(); minHeap.pop();
            maxHeap.push(tmp2);
            minHeap.push(tmp1);
        }

        cout << maxHeap.top() << "\n";
    }
}