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

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

1655번: 가운데를 말해요

 

우선순위 큐 문제다.

 

8개월 전에도 이 문제를 만났었다.

그 때는 벡터를 이용해 넣을 때마다 정렬하고 중앙값을 뽑아내는 작업으로 당연히 시간초과가 났다.

 

그리고 오늘 이 문제를 다시 만났다.

이 문제가 우선순위 큐를 이용한다는 것은 알고 있었다.

그러나 시간 복잡도를 계산했을 때 1000만이 넘어가 0.1초 보다 더 걸릴 것이라고 생각했다.

그리고 시간이 그렇게 걸릴 뿐만 아니라 우선순위 큐는 우선순위가 가장 높은 값만 접근할 수 있기에 중앙값에 바로 접근이 불가능하다.

 

그래서 생각한 게 중앙값이라는 기준점을 하나두고 이보다 작은 우선순위 큐, 큰 우선순위 큐를 만들었다.

이 때 기준점으로 잡아 둔 중앙값과 가장 가까운 값들이 필요하므로 작은 pq는 오름차순으로, 큰 pq는 내림차순으로 했다.

 

코드의 로직은 처음 입력 값을 중앙값으로 이 후 부터는 두 가지 경우로 나뉜다.

수의 개수가 짝수인 경우 두 중앙값 중 작은 값을 출력하므로 큰 pq를 채운다.

수의 개수가 홀수인 경우 양 pq의 사이즈를 같게 만든다.

 

두 경우에서도 각각 두 가지 경우가 존재한다.

짝수인 경우

- 현재 입력 받은 수 >= 이전 중앙값 : 현재 입력 받은 수를 큰 pq에 push한다.

- 현재 입력 받은 수 < 이전 중앙값 : 이전 중앙값을 큰 pq에 push하고 중앙값을 바꾼다.

이 때 발생하는 문제가 있다. 예를 들어 2, 5, 3, 1이 들어오는 경우

  작은 pq : 2 

  큰 pq : 5

  중앙값 : 3

인 상태에서 위의 작업만 수행하면

  작은 pq : 2 

  큰 pq : 3 5

  중앙값 : 1

이 되고, 답이 아니다.

 

따라서 중앙값이 바뀌는 경우 작은 pq의 가장 큰 값과 현재 중앙값을 비교해 스위치 해주는 작업이 필요하다.

  작은 pq : 1 

  큰 pq : 3 5

  중앙값 : 2

로 답을 찾을 수 있다.

 

홀수인 경우도 마찬가지다.

 

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

int n, res;
priority_queue<int> small;
priority_queue<int, vector<int>, greater<int>> big;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	cin >> n;
	cin >> res;
	cout << res << "\n";

	for (int i = 2; i <= n; i++) {
		int a;	cin >> a;
		if (i % 2 == 0) {
			if (res > a) {
				big.push(res);
				res = a;

				if (small.size() && small.top() > res) {
					small.push(res);
					res = small.top();
					small.pop();
				}

			}
			else big.push(a);
		}
		else {
			if (res < a) {
				small.push(res);
				res = a;

				if (big.size() && big.top() < res) {
					big.push(res);
					res = big.top();
					big.pop();
				}

			}
			else small.push(a);
		}
		cout << res << "\n";;
	}

}

 

우선순이 큐를 이용하여 푸는 문제들과 달리 일반적인 풀이법이 아닌 것 같은데

혼자 생각해서 떠올린 게 뿌듯한 문제는 오랜만이다.