[C++] 백준/Gold/1655. 가운데를 말해요

문제: 가운데를 말해요(백준 1655번)

문제 분석

입력이 주어질때마다 중간값을 출력하면 되는 간단명료한 문제이다.

본인이 생각한 방법은 maxHeap과 minHeap의 top을 중간값으로 보고 두 우선순위큐의 size 밸런스를 맞추는 것이다.

오름차순으로 정렬된 배열을 절반으로 나눠서 앞부분을 maxHeap 뒷부분을 minHeap으로 본다고 생각하면 쉽다.

 

우선 입력이 주어졌을때 4가지 분기가 있다.

1. 빈 큐가 있을때

2. 주어진 숫자가 maxHeap의 top보다 작거나 같을때

3. 주어진 숫자가 maxHeap의 top보다 크고 minHeap의 top보다 작을때

4. 주어진 숫자가 minHeap의 top보다 크거나 같을때

 

두 큐가 모두 비어있으면 maxHeap에 입력값을 넣고 minHeap만 비어있다면 maxHeap의 top이 더 작은 수가 오도록 한다.

if (maxHeap.empty()) {
    maxHeap.push(num);
}
else if (minHeap.empty()) {
    if (num < maxHeap.top()) {
        minHeap.push(maxHeap.top());
        maxHeap.pop();
        maxHeap.push(num);
    }
    else {
        minHeap.push(num);
    }
}

주어진 숫자가 maxHeap의 top보다 작거나 같을때 maxHeap의 size가 minHeap보다 크지 않다면 maxHeap에 삽입하고, maxHeap의 size가 더 크다면 maxHeap의 top을 minHeap으로 보내고 수를 넣는다.

else if (num <= maxHeap.top()) {
			if (maxHeap.size() > minHeap.size()) {
				minHeap.push(maxHeap.top());
				maxHeap.pop();
				maxHeap.push(num);
			}
			else {
				maxHeap.push(num);
			}
		}

주어진 숫자가 maxHeap의 top과 minHeap의 top 사이의 값이라면 둘 중 사이즈가 더 작은 큐에 넣는다.

else if (num > maxHeap.top() && num < minHeap.top()) {
			if (maxHeap.size() > minHeap.size())minHeap.push(num);
			else maxHeap.push(num);
		}

주어진 숫자가 minHeap의 top보다 크거나 같을때 minHeap의 size가 maxHeap보다 크지 않다면 minHeap에 삽입하고 minHeap의 size가 더 크다면 minHeap의 top을 maxHeap으로 보내고 수를 넣는다.

    else if(num >= minHeap.top()){
        if (minHeap.size() > maxHeap.size()) {
            maxHeap.push(minHeap.top());
            minHeap.pop();
            minHeap.push(num);
        }
        else {
            minHeap.push(num);
        }
    }

이렇게 숫자를 두 큐에 삽입을 하고 난뒤 두 큐중에 size가 더 큰값의 top이 중간값이다. 만약 두 큐가 size가 같다면 두 큐의 top 중 작은 값을 출력하면 된다.

if (maxHeap.size() > minHeap.size())cout << maxHeap.top() << '\n';
if (maxHeap.size() < minHeap.size())cout << minHeap.top() << '\n';
if (maxHeap.size() == minHeap.size())cout << min(maxHeap.top(), minHeap.top()) << '\n';

 

전체 코드

#include <bits/stdc++.h>
using namespace std;

int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	int n; cin >> n;
	priority_queue<int> maxHeap;
	priority_queue<int, vector<int>, greater<int>> minHeap;

	while (n--) {
		int num; cin >> num;
		if (maxHeap.empty()) {
			maxHeap.push(num);
		}
		else if (minHeap.empty()) {
			if (num < maxHeap.top()) {
				minHeap.push(maxHeap.top());
				maxHeap.pop();
				maxHeap.push(num);
			}
			else {
				minHeap.push(num);
			}
		}
		else if (num <= maxHeap.top()) {
			if (maxHeap.size() > minHeap.size()) {
				minHeap.push(maxHeap.top());
				maxHeap.pop();
				maxHeap.push(num);
			}
			else {
				maxHeap.push(num);
			}
		}
		else if (num > maxHeap.top() && num < minHeap.top()) {
			if (maxHeap.size() > minHeap.size())minHeap.push(num);
			else maxHeap.push(num);
		}
		else if(num >= minHeap.top()){
			if (minHeap.size() > maxHeap.size()) {
				maxHeap.push(minHeap.top());
				minHeap.pop();
				minHeap.push(num);
			}
			else {
				minHeap.push(num);
			}
		}
		if (maxHeap.size() > minHeap.size())cout << maxHeap.top() << '\n';
		if (maxHeap.size() < minHeap.size())cout << minHeap.top() << '\n';
		if (maxHeap.size() == minHeap.size())cout << min(maxHeap.top(), minHeap.top()) << '\n';
	}
}