백준 1655번 가운데를 말해요 - C++(cpp) 풀이

---

 

1. 새 수가 들어오면, 이전 중간값보다 작거나 같다면 최대우선순위큐에, 크다면 최소우선순위큐에 넣는다.
2. 최대우선순위큐에 담긴 수의 개수를 절반으로 유지시킨다.
3. 최대우선순위큐의 top을 출력한다.

 

1. 새 수가 들어오면, 이전 중간값보다 작거나 같다면 최대우선순위큐에, 크다면 최소우선순위큐에 넣는다.

 현재까지 입력받은 수들을 오름차순 정렬했을 때 왼쪽 절반을 최대 우선순위큐에, 오른쪽 절반을 최소 우선순위큐에 보관하는 방식을 사용할 것이다. 그리고 최대 우선순위큐(작은 수들이 담긴 큐)에 담긴 숫자의 수는 항상 전체 개수의 절반으로 유지할 것이다. 이렇게 되면 항상 최대 우선순위큐의 top이 중간값이 된다.

 새로 들어온 수가 왼쪽 절반에 속한다면, 즉 중간값(최대 우선순위큐의 top)보다 작거나 같다면 최대 우선순위큐에 넣는다. 반대로 오른쪽 절반에 속한다면, 즉 중간값보다 크다면 최소 우선순위 큐에 넣는다.

 

2. 최대우선순위큐에 담긴 수의 개수를 절반으로 유지시킨다.

 최대 우선순위큐에 담긴 숫자의 수를 항상 전체 개수의 절반으로 유지시켜준다. 만약 전체 개수의 절반보다 적은 상태라면 최소 우선순위큐에서 팝해와서 더 채워준다. 반대로 전체 개수의 절반보다 많다면 팝해서 최소 우선순위큐로 넘겨준다.

 

3. 최대우선순위큐의 top을 출력한다.

 이제 최대 우선순위큐에는 오름차순 정렬했을 때 왼쪽 절반에 속하는 수들이 들어있으므로, 그 중에서 가장 큰 수가 중간값이 된다.

반응형

---

#include <iostream>
#include <queue>

using namespace std;

int N;
priority_queue<int, vector<int>, less<int>> max_pq;
priority_queue<int, vector<int>, greater<int>> min_pq;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    cin >> N;
    
    int x;
    for (int i=0; i<N; i++) {
        cin >> x;
        
        if (max_pq.empty() || x <= max_pq.top()) {
            max_pq.push(x);
        }
        else {
            min_pq.push(x);
        }
        
        while (max_pq.size() < i / 2 + 1) {
            max_pq.push(min_pq.top());
            min_pq.pop();
        }
        
        while (max_pq.size() > i / 2 + 1) {
            min_pq.push(max_pq.top());
            max_pq.pop();
        }
        
        cout << max_pq.top() << "\n";
    }

    return 0;
}