[알고리즘 풀이 분석] BOJ 1655 가운데를 말해요

우선순위 큐 (힙)을 이용한 알고리즘 문제로 BOJ 의 가운데를 말해요 문제를 포스팅 해 보려 한다!

BOJ 1655 가운데를 말해요

문제는 여기서 확인

문제 목표

정수가 반복적으로 주어질 때 마다 그동안 입력된 수 들 중 중간 값을 구하여 출력

제한 사항

• 주어지는 정수는 1개 이상 100,000개 이하
• 주어지는 정수는 -10,000보다 크거나 같고, 10,000보다 작거나 같음
• 그동안 주어진 정수가 짝수개라면 중간에 있는 두 수 중에서 작은 수를 출력

나의 풀이

먼저 단순하게 배열을 이용해 주어지는 수 마다 올바른 자리를 찾아 해당 자리에 넣고, 배열의 index 값을 이용해 중간 값을 출력하는 방법을 생각했지만,

우선순위 큐를 사용하는 문제에 이는 해답이 아닐 것이라 예상하였고, 무엇보다도 시간 복잡도에서 통과 할 수 없을 것이 분명했다.

N개의 정수를 입력받을 때 각 수를 입력 받아 자리를 찾을 때 마다 N, 이를 N개의 정수마다 반복하면 O(N^2) 의 시간 복잡도를 갖게 되고, 힙을 사용하라는 것을 보아 분명 최소한 O(NlogN) 의 시간 복잡도를 만족 시켜야 할 것이었다.

힙을 사용해서 고민해 보았지만,, 결론부터 말하자면 적당한 묘안을 생각해 내지 못했고, 한 포스팅에서 아이디어를 얻어 구현하였다


알고리즘은 다음과 같다

1. 주어지는 수들을 절반으로 나누어 작을 쪽은 최대힙, 큰 쪽은 최소 힙으로 관리한다
2. 최대힙.size() == 최소힙.size() || 최대힙.size() == 최소힙.size() + 1 로 유지하고
3. 중간값은 최대힙.top() 으로 도출한다
4. 매번 새로운 정수가 입력되면 이전의 중간값과 비교하여 삽입한다
5. 도출되어 있는 중간값보다 작거나 같으면 최대힙에, 크면 최소힙에 삽입한다.
6. 이후 조건 2에 맞추어 최대힙.top() 을 최소힙으로 혹은, 최소힙.top()을 최대힙으로 옮겨 새로운 중간 값을 도출한다.
   
   
   작성코드

#include <iostream>
#include <queue>
#include <vector>

// BOJ 1655 가운데를 말해요, 우선순위 큐 사용, 배열을 절반으로 나누는 것이 핵심!
using namespace std;

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

int getMiddleNumber(int newNumber){
    int total = maxHeap.size() + minHeap.size();
    int mid = maxHeap.top();
    int trans;

    if (newNumber <= mid) maxHeap.push(newNumber);
    else minHeap.push(newNumber);

    if (maxHeap.size() == minHeap.size()+2){
        trans = maxHeap.top();
        maxHeap.pop();
        minHeap.push(trans);
    }else if(maxHeap.size() +1 == minHeap.size()){
        trans = minHeap.top();
        minHeap.pop();
        maxHeap.push(trans);
    }

    return maxHeap.top();
}

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

    int num;
    cin>>num;

    vector<int> answer;
    maxHeap.push(num);
    answer.push_back(maxHeap.top());

    for (int i = 0; i < N-1 ; ++i) {
        cin>>num;
        int mid = getMiddleNumber(num);
        answer.push_back(mid);
    }

    for (int i = 0; i < answer.size(); ++i) {
        cout<<answer[i]<<'\n';
    }
    return 0;
}

100% 내 힘으로 푼 것이 아니기에 잊지 않으려고 일부러 포스팅을 한다!
중간 값을 기준으로 배열을 절반으로 나누고, 최대힙, 최소힙의 특징을 이용하는 것이 핵심!


💡해당 풀이는 다음 자료를 참고하였습니다!


❗️포스팅 관련 문제가 있다면 댓글, 메일로 연락주세요!🙆🏻‍♀️