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

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

1655번: 가운데를 말해요

 

입력되는 수들의 가장 작은 수에서 중앙값의 수 범위의 수들은 최대 힙에 저장하여 해당 힙의 top에 중앙값이 위치하도록 하고, 중앙값보다 큰 범위의 수들은 최소 힙에 저장하여 해당 힙의 top에 중앙값보다 큰 수중에서 가장 작은 값이 위치하도록 하여 중앙값을 관리하는 방법으로 문제를 해결했다.

 

코드

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

int n;
vector<int> result;
priority_queue<int> max_pq; //가장작은수 ~ 중앙값의 수 (최대힙)
priority_queue<int, vector<int>, greater<int>> min_pq; //중앙값보다 큰 수 (최소힙)

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	cin >> n;

	for (int i = 0; i < n; i++) {
		int input;
		cin >> input;

		if (i == 0) {
			max_pq.push(input);
			result.push_back(input);
			continue;
		}

		//최대힙과 최소힙의 크기가 같을때
		//최대힙의 크기가 증가해야 된다
		if (max_pq.size() == min_pq.size()) {

			//중앙값을 교체해야 될때
			//현재 중앙값 보다 큰 수 중에서 가장 작은값을 중앙값으로 교체한다
			if (max_pq.top() < input) {
				min_pq.push(input);
				max_pq.push(min_pq.top()); //최소힙의 가장 작은 값을 최대힙에 넣는다
				min_pq.pop();
			}

			//중앙값을 교체하지 않아도 될때
			else {
				max_pq.push(input);
			}
		}

		//최소힙의 크기가 더 작을때
		//최소힙의 크기가 증가해야 된다
		else {

			//중앙값을 교체해야 될때
			if (max_pq.top() > input) {
				max_pq.push(input);
				min_pq.push(max_pq.top()); //최대힙의 가장 큰 값을 최소힙에 넣는다
				max_pq.pop();
			}

			//중앙값을 교체하지 않아도 될때
			else {
				min_pq.push(input);
			}
		}

		result.push_back(max_pq.top());
	}

	for (int i = 0; i < result.size(); i++) {
		cout << result[i] << "\n";
	}

}