[C++/BOJ] 가운데를 말해요

🏅 Gold 2

✏️ 1차 솔루션

heap 로 구현 ➡️ 우선순위 큐 활용
최대 heap 와 최소 heap 를 두고 최대 heap 는 오름차순 정렬, 최소 heap 는 내림차순 정렬해서 최대 heap 중 최소값, 최소 heap 중 최대값이 각각 top 에 위치하도록 하기

1. 첫번째 숫자의 경우, 두 개의 heap 모두 비어있기 때문에 최소 heap 에 넣어주기
2. 최소 heap 의 top 보다 현재 숫자가 작으면 최소 heap 에 넣어주고 아니면 최대 heap 에 넣어주기
3. 현재까지 부른 숫자가 홀수개면 크기가 더 큰 heap 의 top 값을 return ➡️ 이 값이 가운데 숫자
4. 현재까지 부른 숫자가 짝수개면 크기가 더 큰 heap 의 top 값을 다른 heap 에 push 하고 pop 하기 ➡️ 중간값을 구하기 위해 밸런스를 맞춰주는 과정
5. 현재까지 부른 숫자가 짝수개이면 가운데 있는 수 중에 작은 수를 return 해야 하는데 이때 가운데 수는 각 heap 의 top 값이므로 최소 heap 의 top 값을 return

[링크] heap
[링크] 우선순위 큐

🚨 1차 trouble

테케 통과는되지만 틀렸다고 뜬다ㅠ
heap 가 비었을 때의 처리가 미흡하고 최대 heap, 최소 heap 정렬방식에 대한 이해가 미흡해서 설계부터 망함

✏️ 최종 솔루션

heap 를 사용한다는 점은 같지만 전개 방향이 다름

전체 수를 2개의 집합으로 분류한다고 가정했을 때

• 최대 heap: 작은 값들 중 최대값이 top ➡️ 내림차순 정렬
• 최소 heap: 큰 값들 중 최소값이 top ➡️ 오름차순 정렬

1. 최대 heap 와 최소 heap의 size 가 같으면 최대 heap에 push, 아니면 최소 heap에 push
   ➡️ 두 heap가 모두 empty 인 초기 상태에서 최대 heap에 넣어주면서 시작(예외처리 가능)
   ➡️ 현재까지의 숫자가 홀수개일 경우, 한쪽 heap 개수가 많아질 수밖에 없기 때문에 한쪽이 많아져도 문제 없음
   ➡️ size 가 같지 않을 경우, 최대 heap 개수가 많은 상황이므로 최소 heap에 push해서 균형 맞출 수 있음
2. 앞에서 heap size에 따라 무작정 push 했기 때문에 숫자 순서대로 정렬이 안 되어 있을 수 있는 경우 예외 처리 ex) 최대 heap의 최대값이 최소 heap의 최소값보다 큰 경우
   ➡️ 두 값을 swap 해서 원상복구
3. 항상 최대 heap에 우선 push하고 최대 heap가 작은 값들의 집합이기 때문에 최대 heap의 top 값을 return

📌 self feedback

heap 를 사용해야한다는 점을 생각하는 것을 넘어 어떻게 구현할지 계획하는 것이 관건인 문제

1. 초기에 두 heap 모두 empty 인 상황에서 어떻게 처리할지
2. 한 쪽 heap의 개수가 계속 증가하지 않고 균형을 맞추면서 push하려면 어떻게 해야할지

이 2가지를 구현하는 것이 헷갈렸음

일단 균형을 맞출 수 있도록 push 하고 어차피 자동 정렬되기 때문에 순서가 맞지 않을 top 값만 swap 해주면 깔끔하게 풀 수 있는 문제였음
heap 에 push하기 전에 값을 비교하고 그때마다 push, pop을 빈번하게 할 필요가 없음

✏️ 최종 code

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

using namespace std;

int main() {
	
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    int n;
    cin >> n;
    
    priority_queue <int> max;    //작은 것들 중 max - 내림차순
    priority_queue<int,vector<int>,greater<int>> min;    //큰 것들 중 min - 오름차순
    
    int num;
    for(int i=1;i<=n;i++) {
        cin >> num;
        
        if(max.size()==min.size()) max.push(num);
        else min.push(num);
        
        // max와 min의 순서가 맞지 않을 경우 swap
        if(!max.empty() && !min.empty() && max.top()>min.top()) {
            int mx,mn;
            mx=max.top();
            mn=min.top();
            
            max.pop();
            min.pop();
            
            min.push(mx);
            max.push(mn);
        }
        
        cout << max.top() << '\n';
    }
}