문제 출처

1. 문제설명

  • 백준이가 정수를 하나씩 외칠때마다 동생은 지금까지 백준이가 말한 수 중에서 중간 값을 말한다.
  • 만약 백준이가 외친 수가 짝수개라면 중간에 있는 두 수 중에서 작은 수를 말해야 한다.
  • 백준이가 외치는 수가 주어졌을 때, 동생이 말해야 하는 수를 구하라.



2. 알고리즘 설계

  • 시간 제한이 0.1초이면서 N은 100,000이었다.
  • 무조건 $O(lgN)$으로 풀어야하는데, 다행이 priority_queue가 있었다.
  • max_heap, min_heap을 각각 이용해 풀 수 있는 문제였다.



3. 로직

  • pq에 담는 규칙은 간단하다.
    • 입력되는 원소를 push한다.
      • 만약 max_heap의 크기가 더 크다면 min_heap에 push
      • 그렇지 않다면, max_heap에 push
    • min_heap의 top이 max_heap의 top보다 작다면
      • 서로의 값을 바꿔준다.
    • 현재의 top 값을 출력한다.



4. 전체 코드

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

int main(void)
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);

	int n; 
	cin >> n;
	
	priority_queue<int> max_pq;
	priority_queue<int> min_pq;
	while (n--) {
		int tmp; cin >> tmp;
		
		if (max_pq.size() > min_pq.size()) min_pq.push(~tmp);
		else max_pq.push(tmp);

		if (!max_pq.empty() && !min_pq.empty()) {
			int a = max_pq.top(); 
			int b = ~min_pq.top();

			if (a > b) {
				max_pq.pop();
				min_pq.pop();

				max_pq.push(b);
				min_pq.push(~a);
			}
		}
		cout << max_pq.top() << '\n';
	}
	
	return 0;
}



5. 소감

  • 우선순위 큐를 두개 사용하는 로직은 처음이었다.
  • 방법을 이해하는데 매우 어려웠다.
  • 다른 개발자의 코드를 디버깅해보면서 이해할 수 있었다….