[C++] 1655. 가운데를 말해요 (ft.Priority Queue)

출처

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

 

 

문제

백준이는 동생에게 "가운데를 말해요" 게임을 가르쳐주고 있다. 백준이가 정수를 하나씩 외칠때마다 동생은 지금까지 백준이가 말한 수 중에서 중간값을 말해야 한다. 만약, 그동안 백준이가 외친 수의 개수가 짝수개라면 중간에 있는 두 수 중에서 작은 수를 말해야 한다.

예를 들어 백준이가 동생에게 1, 5, 2, 10, -99, 7, 5를 순서대로 외쳤다고 하면, 동생은 1, 1, 2, 2, 2, 2, 5를 차례대로 말해야 한다. 백준이가 외치는 수가 주어졌을 때, 동생이 말해야 하는 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에는 백준이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 백준이가 외치는 정수가 차례대로 주어진다. 정수는 -10,000보다 크거나 같고, 10,000보다 작거나 같다.

 

출력

한 줄에 하나씩 N줄에 걸쳐 백준이의 동생이 말해야 하는 수를 순서대로 출력한다.

 

 

풀이

부캠에서 PQ를 배우며 풀어본 문제.

사실상 힌트를 거의 받으면서 푼거나 다름없다!!!

목표는 mid를 구하는 것이다! 따라서 mid를 기준으로 왼쪽-오른쪽의 개수를 비교해가며 풀면 된다.

짝수개가 입력되었을 때는, 작은 수들의 개수(왼쪽)가 큰 수들의 개수(오른쪽)보다 1이 작다.

홀수개가 입력되었을 때는, 작은 수들의 개수(왼쪽)와 큰 수들의 개수(오른쪽)가 같아야 한다.

이를 활용해서 max_heap(왼쪽)과 min_heap(오른쪽) 두개를 활용하여 풀이한다.

일단 mid를 기준으로 max_heap과 min_heap 둘 중 한 곳에 넣는다.

여기서 mid보다 작은 수는 max_heap, mid보다 큰 수는 min_heap을 사용해야 한다!!

#include <bits/stdc++.h>
using namespace std;

int N;
vector<int> result;
priority_queue<int> lesser_heap;
priority_queue<int, vector<int>, greater<int>> bigger_heap;


// 1. 값을 입력받는다.
// 3. 만약 입력받은 값이 mid보다 큰데, bigger_heap의 개수도 lesser_heap의 개수보다 크면, 입력 값 = mid & 원래 mid 값을 lesser에 넣는다.
// 2. 만약 입력받은 값이 mid보다 작은데, lesser_heap의 개수도 bigger_heap의 개수보다 2 이상 작으면(그럴 수 있나?), 입력 값 = mid & 원래 mid 값을 bigger에 넣는다.
void solution() {
	int mid;
	cin >> N;
	result.resize(N);
	cin >> mid;
	result[0] = mid;
	for (int i = 1; i < N; ++i) {
		int num;
		cin >> num;
		if (num > mid) { 
			bigger_heap.push(num); 
		}
		else { 
			lesser_heap.push(num); 
		}
		if (lesser_heap.size() > bigger_heap.size()) {
			bigger_heap.push(mid);
			mid = lesser_heap.top();
			lesser_heap.pop();
		}
		else if (bigger_heap.size() - lesser_heap.size() == 2) {
			lesser_heap.push(mid);
			mid = bigger_heap.top();
			bigger_heap.pop();
		}
		result[i] = mid;

	}
}

void print_result() {
	for (int i = 0; i < N; ++i){
		cout << result[i] << "\n";
	}
	cout << endl;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	solution();
	print_result();
}

 

설계 시간이 살짝 부족해서 바로 구현으로 넘어갔더니, 중간에 mid를 바꿔주는 과정에서 헷갈리는 부분이 있었다. 앞으로는 설계에 시간을 더 투자해야겠다.