백준 1655 가운데를말해요 c++ // 우선순위큐 2개로 정렬효과만들기

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

1655번: 가운데를 말해요

1.시간복잡도

정렬후 mid 인덱스 출력 - > N ( 10만) * NlgN(정렬) -> 시초

특정알고리즘 필요 : pq, dp, 이분탐색 등..

정렬한효과 -> pq 2개로 구현

 

2. 의사코드

maxHeap의 top이 항상 중간값이 되도록 고정하면 자동정렬이 된다.

이럴려먼 maxHeap의 크기가 minHeap의 크기보다 같거나 1이 커야한다.

 

1. 입력온값을 어디에 넣을것인가?

max.top <=입력 -> minHeap에 넣기

else : maxHeap에 넣기

 

2. 한쪽큐에 쏠린경우 재조정

오른쪽에 쏠린경우 : max.size < min.size 인경우 : 우측에서 좌로 옮겨주기

좌측에쏠린경우 : max,size > min.size+1인 경우 : 좌에서 우로 옮겨주기

 

3. 전체코드

#include <bits/stdc++.h>

using namespace std;

priority_queue<int, vector<int>> pq1; //최대힙
priority_queue<int, vector<int>,greater<int>> pq2; //최소힙
int n,tmp;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n;
	for (int i = 0; i < n; ++i) {
		cin >> tmp;
		if (i == 0) {
			pq1.push(tmp);
			cout << tmp << "\n";
			continue;
		}

		if (pq1.top() <= tmp) {
			pq2.push(tmp);
		}
		else {
			pq1.push(tmp);
		}

		//재조정
		if (pq1.size() < pq2.size()) {
			int temp = pq2.top(); pq2.pop();
			pq1.push(temp);
		}
		if (pq1.size() > pq2.size()+1) {
			int temp = pq1.top(); pq1.pop();
			pq2.push(temp);
		}

		cout << pq1.top() << "\n";

	}


	
	return 0;
}