[백준 1655번] 가운데를 말해요

문제 링크: https://www.acmicpc.net/problem/1655

1655번: 가운데를 말해요

<문제 풀이> 우선순위 큐

https://seokjin2.tistory.com/37

[백준 2696번] 중앙값 구하기

백준 2696번 에서는 홀수 번째 수를 읽었을 때만 중앙값을 출력해주었는데 1655번은 짝수 번째 수를 읽었을 때도 중앙값을 출력해주도록 추가해주면 됩니다.

 

짝수 번째 수를 읽었을 때는 최대 힙과 최소 힙 중에 사이즈가 큰 힙에 top과 이전에 구했던 중앙값 중 작은 값을 출력하면 됩니다.

 

왜냐하면 2696번 알고리즘을 그대로 적용하면 짝수 번째 수를 읽었을 때 중앙값을 기준으로 했을때 사이즈가 큰 힙 쪽에 원소가 더 치우쳐져 있으므로 사이즈 큰 쪽에 top을 가운데 수로 택해야 합니다.

ex) maxHip(1, 2) , mid(3), minHip(4) -> 여기서 2를 택해서 2 와 3의 최솟값을 출력

 

[알고리즘]

1. 최대 힙과 최소 힙을 준비한다.

2. 첫 번째 수를 중앙값으로 한다.

3. 두 번째부터 입력받은 수를 중앙값과 비교해서 작으면 최대 힙, 크면 최소 힙에 push한다.

4. 홀수 번째라면 최대 힙과 최소 힙 중에 사이즈가 작은 힙에 중앙값을 push 하고 그리고 힙 중에 사이즈가 큰 힙의 top을 중앙값으로 한다.

5. 짝수 번째라면 최대 힙과 최소 힙 중에 사이즈가 큰 힙에 top과 최근에 구했던 중앙값 중 작은 값을 출력해주면 된다.

 

 

<C++ 소스 코드>

#include <iostream>
#include <queue>
using namespace std;
 
int main(void) {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
 
    int m;
    cin >> m;
    int data;
    int mid;
    priority_queue<int> max_pq;
    priority_queue<int, vector<int>, greater<int> > min_pq;
    vector<int> ans;
    cin >> data;
    mid = data;
    ans.push_back(mid); //1개 일때는 그 수가 mid
    for (int i = 2; i <= m; i++) {
        cin >> data;
        if (data < mid)max_pq.push(data); //data를 mid 보다 작으면 최대힙 크면 최소힙에 넣는다
        else min_pq.push(data);
        int max_pq_size = max_pq.size();
        int min_pq_size = min_pq.size();
        if (i % 2 == 1) { //홀수 번째 수를 읽을 때 마다
            if (max_pq_size < min_pq_size) { //최대 힙과 최소 힙 중에 사이즈가 작은 힙에 mid를 push
                max_pq.push(mid);
                max_pq_size++;
            }
            else {
                min_pq.push(mid);
                min_pq_size++;
            }
 
            if (max_pq_size > min_pq_size) { // 힙 중에 사이즈가 큰 힙의 top이 mid가 됨
                mid = max_pq.top();
                max_pq.pop();
            }
            else {
                mid = min_pq.top();
                min_pq.pop();
            }
            ans.push_back(mid);
        }
        else {//짝수 번쨰 수를 읽을 때는 최대 힙과 최소 힙중에 사이즈가 큰 쪽의 top과 mid중 작은값을 출력
            if (max_pq_size > min_pq_size) ans.push_back(min(max_pq.top(), mid));
            else ans.push_back(min(min_pq.top(), mid));
        }
    }
    for (auto& e : ans) cout << e << "\n";
 
    return 0;
}