BOJ/백준 - 1665 가운데를 말해요 C++

가운데를 말해보자!!!!!!

www.acmicpc.net/problem/1655

1655번: 가운데를 말해요

이거는..이거는 진짜 헷갈렸다

 

최대힙과 최소힙을 사용해서 문제를 풀어보자.

최대힙 : 값이 클 수록 우선순위 큼

최소힙 : 값이 작을 수록 우선순위 큼 

*maxHeap의 top값은 중간값과 작거나 같아야 함

 

이렇게 만들거고, 이 개념을 토대로 중간값을 구하면 된다.

그래서 입력된 수열들의 중간값을 기준으로 각각 maxHeap, minHeap에 넣을것이다.

 

다음과 같은 조건 만족해야 함

1. maxHeap의 size는 minHeap의 size보다 1만큼 크거나 같다.

2. maxHeap의 top은 minHeap의 top보다 작거나 같아야 한다.

 

풀이

(1)

홀수개가 입력되면 maxHeap의 size가 1 더 클 것이다.

짝수개가 입력되면 maxHeap의 size와 minHeap의 size가 같을 것이다.

=maxHeap의 size는 minHeap의 size보다 1만큼 크거나 같다.

 

(2)

maxHeap의 top은 minHeap의 top보다 작거나 같아야 한다.

만약 maxHeap의 top이 minHeap의 top보다 크다면 swap해준다.

 

(3) 

중간값 출력

#include <iostream>
#include <queue>
 
using namespace std;
 
int main() {
    cin.tie(NULL);
    ios_base::sync_with_stdio(false);
    int n;
    cin >> n;
    priority_queue<int> maxHeap, minHeap;
 
    for (int i = 0; i < n; i++) {
        int tmp;
        cin >> tmp;
 
        //(1)
        if (maxHeap.size() > minHeap.size()) minHeap.push(-tmp);
        else maxHeap.push(tmp);
 
        //(2)
        if (!maxHeap.empty() && !minHeap.empty()) {
            if (-minHeap.top() < maxHeap.top()) {
                int max_val = maxHeap.top();
                int min_val = -minHeap.top();
 
                maxHeap.pop(); minHeap.pop();
 
                maxHeap.push(min_val);
                minHeap.push(-max_val);
            }
        }
 
        //(3)
        cout << maxHeap.top() << '\n';
    }
    return 0;
}