[C++]백준 1655번: 가운데를 말해요

문제

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

1655번: 가운데를 말해요

 

문제이해

 

 

• 첫째 줄에 정수의 개수(N)을 입력합니다.
• 다음 줄부터 N개의 수를 입력합니다.
• N번의 케이스 동안의 중간값을 N개의 줄을 통해 출력합니다.

문제 자체의 내용은 매우 간단하지만 시간 제한이 0.1초이기 때문에 무엇인가 색다른 방법이 필요합니다. 처음엔 priority_queue 한개에 자료를 넣고 중간 값을 찾아가 이를 vector에 저장하고 나중에 출력하는 방법을 사용했습니다. 그러나 이렇게 하면 priority_queue의 중간 값을 찾기 위해 O(n)의 시간복잡도를 가지게 되고 시간초과가 날 수 밖에 없었습니다. 도저히 방법이 생각나지 않아 힌트를 보고 풀었고 해답은 다음과 같았습니다.

 

1. priority_queue를 두개 준비합니다. 하나는 max_heap이고 다른 하나는 min_heap입니다.
2. max_heap의 top값이 배열의 중간값이 되도록 합니다.
3. max_heap의 top값이 배열의 중간값이 되도록 하기위해서는 max_heap의 크기가 min_heap의 크기보다 1 크거나 같아야 합니다.
4. 만약 max_heap의 top 값이 min_heap의 top 값보다 크다면 두 값을 바꿔 총 배열이 오름차순이 되도록 수정해줘야 합니다.

 

다음은 위의 해답으로 만든 코드 입니다.

문제해결

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

priority_queue<int, vector<int>> max_;
priority_queue<int, vector<int>, greater<int>> min_;
vector<int> store;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int N, D;
	cin >> N;
	for (int i{ 0 }; i < N; i++) {
		cin >> D;
		store.push_back(D);
	}
	for (int i{ 0 }; i < N; i++) {
		D = store[i];
		if (max_.size() == min_.size() + 1) {
			min_.push(D);
		}
		else {
			max_.push(D);
		}
		if (max_.size() != 0 && min_.size() != 0) {
			if (max_.top() > min_.top()) {
				int A = max_.top();
				int B = min_.top();
				max_.pop();
				min_.pop();
				max_.push(B);
				min_.push(A);
			}
		}
		cout << max_.top() << "\n";
	}
}

 

문제후기

배열을 두개로 나누어 저장한다는 점을 생각하지 못해 한참을 헤맸습니다.