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

https://www.acmicpc.net/problem/1655

 

부른 수들 중에서 중간값을 찾아내야 한다. 짝수개면 둘 중 더 작은거

무작위로 부른 수들의 정렬이 필요하니 우선순위 큐를 사용해야 함을  생각할 수 있다.

 

예시인 1, 5, 2, 10, -99, 7, 5 을 생각해보면

크기순 정렬하면 -99, 1, 2, 5, 5, 7, 10이 되고 중간은 5가 된다.

이걸 왼쪽(작은값들)과 오른쪽(큰값들)으로 나눠서 생각해보자. 이러는 이유는 우선순위큐에서 우리가 쓸 수 있는 값은 어쨌든 top값밖에 없기 때문이다. 중간에 든 걸 뺄 수가 없는 구조니까 우린 중간값이 top에 오도록 만들어주는 편이 좋다.

그렇다면 왼쪽(작은값들)은 내림차순(최대히프)으로,

오른쪽(큰값들)은 오름차순(최소히프)으로 정렬해준다면, 각 부분에서 top이 중간값이 될 수 있을 것이다.

 

중간값을 최대힙에 저장한다치고 구현을 해보자. 그러려면 최대힙의 사이즈가 최소힙보다 같거나 1 더 커야 할 것이다.

수를 입력받고, 윗줄 조건을 만족하는 선에서 힙에 입력받은 수를 푸시한다.

단 이때는 개수 기준으로 저장되므로 입력받은 값이 잘못 저장될 수도 있다. 이를 맞추기 위해 balance라는 함수를 만들어주자.

void balance(priority_queue<int>&max_pq,priority_queue<int, vector<int>, greater<>>&min_pq){
    int max_top = max_pq.top();
    int min_top = min_pq.top();
    
    //작은값들은 최대히프, 큰값들은 최소히프에 저장되어야 함
    if(max_top > min_top){
        //즉 현재 최대히프의 top이 최소히프의 top보다 크다면, 자리를 바꿔주어야 함
        max_pq.pop();
        min_pq.pop();
        
        min_pq.push(max_top);
        max_pq.push(min_top);
    }
}

 

전체 코드

런타임 오류가 한번 났는데, balance를 실행할 때 조건을 주지 않아서였다.

balance는 두 큐의 top값을 보고 실행하는 함수이므로 큐가 비어있다면 실행할 수 없다.

#include <iostream>
#include <queue>

using namespace std;

void balance(priority_queue<int>&max_pq,priority_queue<int, vector<int>, greater<>>&min_pq){
    int max_top = max_pq.top();
    int min_top = min_pq.top();
    
    //작은값들은 최대히프, 큰값들은 최소히프에 저장되어야 함
    if(max_top > min_top){
        //즉 현재 최대히프의 top이 최소히프의 top보다 크다면, 자리를 바꿔주어야 함
        max_pq.pop();
        min_pq.pop();
        
        min_pq.push(max_top);
        max_pq.push(min_top);
    }
}

int main()
{
    ios::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	
    int n, num;
    cin >> n;
    
    priority_queue<int> max_pq;
    priority_queue<int, vector<int>, greater<>> min_pq;
    
    while(n--){
        cin >> num;
        
        if(max_pq.size() > min_pq.size()) {
            //같거나, 최대히프가 하나 더 많도록
            //즉 현재 최대히프사이즈가 더 크다면, 최소히프에 저장해 개수를 맞춰줌
            min_pq.push(num);
        } else {
            max_pq.push(num);
        }
        
        if(!max_pq.empty() && !min_pq.empty()){
            balance(max_pq, min_pq);
        }
        
        //최대히프 top이 중간값이므로 출력
        cout << max_pq.top() << '\n'; 
    }
    
    return 0;
}