백준 1655번 가운데를 말해요

문제링크: https://www.acmicpc.net/problem/1655

사용한 알고리즘: priority_queue(우선순위 큐)


 입력으로 수들이 주어지고, 그 수들의 중간값을 말해주는 문제입니다. sort의 시간복잡도가 O(nlogn) 이므로, 10^5개를 한번만 sort 한다고 쳐도 대략 (10^5)*(log2(10^5)) = 17*10^5 정도이니, 입력이 주어질 때마다 sort를 하게되면 1 + 2*1 + ..... + 17*10^5 가 되므로,
당연히 터지게 됩니다. 따라서 pq 2개를 써서 풀면 되는 문제였습니다.

문제풀이는 다음과 같습니다.
(1) 중간값을 MID 라 하면, MID 를 기준으로 MID보다 작은 값들을 모아, 가장 큰 값이 위로 오게 하는 priority_queue<int, vector<int>, less<int>> MinQ 와 MID를 기준으로 MID보다 큰 값들을 모아, 가장 작은 값이 위로 오게 하는 priority_queue<int, vector<int>, greater<int>> MaxQ 를 각각 만들어 줍니다.

(2) 처음 입력값을 MID 값으로 합니다. 이후 들어오는 수를 MID보다 작으면 MinQ, 크면 MaxQ에 넣어줍니다.

(3) MID 가 중간값인지 확인해야합니다. 입력된 수들의 개수가 홀수개면 MinQ의 개수와 MaxQ의 개수가 같아야 합니다. 다르다면 같게 만들어 줍니다. 예를들어 MinQ (개수 4), MID , MaxQ (개수 2) 이면, MID 를 MaxQ에 넣고, MinQ의 top 값을 빼서 MID 값으로 해줍니다. 이러면 MinQ (개수 3), MID, MaxQ (개수 3) 이 되어 MID 값이 됩니다. 만약 입력된 수들의 개수가 짝수개면 MinQ, MaxQ 개수 차가 1개가 되는데, 개수가 많은쪽의 top값과 MID 값을 비교하여 둘중 작은 값을 출력해주면 됩니다.

	#include <bits/stdc++.h>
	using namespace std;
	int N;
	int MID = 100000;
	priority_queue<int, vector<int>, less<int>> MinQ;
	priority_queue<int, vector<int>, greater<int>> MaxQ;
	void Balence(){
	int left = MinQ.size();
	int right = MaxQ.size();
	if(right==left || abs(right-left)==1) return;
	if(left>right){
	while(1){
	if(right+1==left || right==left) break;
	MaxQ.push(MID);
	right++;
	MID=MinQ.top();
	MinQ.pop();
	}
	}
	else{
	while(1){
	if(left+1==right||left==right) break;
	MinQ.push(MID);
	left++;
	MID=MaxQ.top();
	MaxQ.pop();
	}
	}
	}
	int ans(){
	int temp;
	if(MinQ.size()>MaxQ.size()) temp = MinQ.top();
	else temp = MaxQ.top();
	if(temp<MID) return temp;
	else return MID;
	return 0;
	}
	int main(){ios_base::sync_with_stdio(false); cout.tie(NULL); cin.tie(NULL);
	cin >> N;
	for (int i = 0; i < N; ++i){
	int num;
	cin >> num;
	if(i==0){
	MID = num;
	cout << MID << '\n';
	continue;
	}
	if(MID>num) MinQ.push(num);
	else MaxQ.push(num);
	Balence();
	if(i%2==0) cout << MID << '\n';
	else cout << ans() << '\n';
	}
	return 0;
	}

view raw BOJ 1655.cpp hosted with ❤ by GitHub