BOJ - 1655번 가운데를 말해요(C++)

문제 출처:https://www.acmicpc.net/problem/1655

문제 난이도

Gold 2

문제 접근법

시간 제한이 2초 이긴 해도, 입력 받자마자 계산하고 출력해야하기 때문에 이중 for문 및 정렬을 계속하면 시간 초과가 뜬다.
우선순위 큐를 이용해서, 최소힙과 최대힙으로 중간값을 구한다.

1. maxHeap에 값을 넣고, 그 다음 값은 minHeap에 넣는다(차례로 넣는다)
2. 각 heap의 top만 비교해서 maxHeap의 top이 minHeap의 top보다 크면 교환한다.
3. maxHeap의 top이 중간값이 된다.

왜?

maxHeap의 top은 가지고 있는 값 중 가장 큰 값, minHeap의 top은 가지고 있는 값 중 가장 작은 값이다.
그럼 만약 maxHeap에 작은 수들만 있고 그 중 가장 큰 값이고, minHeap에 큰 수들만 있어서 그 중 가장 작은값이면 maxHeap에 있는 top이 중간값이 되기 때문이다.(문제 조건 중, 짝수 개 일때는 2개가 나오는 데 그 중 작은 값을 출력하라)

통과 코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;


int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int N;
	cin >> N;
	priority_queue<int> maxHeap;
	priority_queue<int,vector<int>,greater<int>> minHeap;
	for (int i = 0; i < N; i++) {
		int x;
		cin >> x;
		if(maxHeap.empty()) maxHeap.push(x);
		else {
			if(maxHeap.size() > minHeap.size()) minHeap.push(x);
			else maxHeap.push(x);
			if (maxHeap.top() > minHeap.top()) {
				int tmp = minHeap.top();
				int tmp2 = maxHeap.top();
				minHeap.pop();
				maxHeap.pop();
				minHeap.push(tmp2);
				maxHeap.push(tmp);
			}
		}
		cout << maxHeap.top() << "\n";
	}
	return 0;
}

피드백

처음에는 multiset(set이지만 중복이 허용)을 사용했는데, 시간 초과가 떴다.
우선순위큐로 top만 비교하는 방법을 생각못했는데 좀 더 유용하게 사용할 수 있을 것 같다.

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>

using namespace std;


int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int N;
	cin >> N;
	multiset<int> arr;
	for (int i = 0; i < N; i++) {
		int x;
		cin >> x;
		arr.insert(x);
		if (arr.size() % 2 == 0) {
			int cnt = 0, res=0, res2=0;
			for (auto x : arr) {
				if (cnt == arr.size() / 2 ) {
					res2 = x;
					break;
				}
				else if (cnt == arr.size() / 2 - 1) {
					res = x;
				}
				cnt++;
			}
			cout <<  min(res, res2) << "\n";
		}
		else {
			int cnt = 0;
			for (auto x : arr) {
				if (cnt == arr.size() / 2) {
					cout <<  x << "\n";
					break;
				}
				cnt++;
			}
		}
	}
	return 0;
}