[백준] 1655-가운데를 말해요(C++)

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

1655번: 가운데를 말해요

 

접근방식

 

1. 시간 제한이 0.1초인 것을 보고 일반적인 정렬 방식을 사용하면 안되는 것을 인지

2. 시간 제한상 nlogn번만에 도출해야 하는 것을 인지하였고 max 힙, min 힙 2개를 사용해서 구현하는 방법을 고안

 

 

문제풀이 

 

1. 음.. 설명하기 어려워서 잘 설명된 링크를 가져왔습니다! ㅋㅋㅋㅋㅋ

https://o-tantk.github.io/posts/finding-median/

tantk land

너무 잘 정리하셨더라구요! 

2. 위에서 설명하는 방식처럼 max힙에는 기준점보다 작은 값, min힙에는 기준값보다 큰 값들로 구성

 

정답코드입니다.

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

int n = 0, temp = 0;

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);

	priority_queue <int> mx; //기준보다 작은 값들을 넣을거 (기준포함)
	priority_queue <int> mn; //기준보다 큰 값들을 넣을거 -1곱하면서

	//초기작업
	cin >> n;

	cin >> temp;
	mx.push(temp);
	cout << temp << "\n";

	for (int i = 1; i < n; i++) {
		cin >> temp;
		int sta = mx.top();
		if (sta > temp) {
			if (mx.size() > mn.size()) {
				mx.pop();
				mn.push(sta*-1);
				mx.push(temp);
			}
			else {
				mx.push(temp);
			}

		}
		else if (sta < temp) {
			if (mx.size() == mn.size()) {
				mn.push(temp*-1);
				int mnn = mn.top()*-1;
				mn.pop();
				mx.push(mnn);
			}
			else {
				mn.push(temp*-1);
			}
		}
		else { //sta == temp
			if (mx.size() == mn.size()) {
				mx.push(temp);
			}
			else { //mx가 하나 더 많을 때
				mn.push(temp*-1);
			}
		}

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

	}


	return 0;
}