개요

백준 2696번: 중앙값 구하기

• 입력
  첫째 줄에 테스트 케이스의 개수 T(1 ≤ T ≤ 1,000)가 주어진다. 각 테스트 케이스의 첫째 줄에는 수열의 크기 M(1 ≤ M ≤ 9999, M은 홀수)이 주어지고, 그 다음 줄부터 이 수열의 원소가 차례대로 주어진다. 원소는 한 줄에 10개씩 나누어져있고, 32비트 부호있는 정수이다.

• 출력
  각 테스트 케이스에 대해 첫째 줄에 출력하는 중앙값의 개수를 출력하고, 둘째 줄에는 홀수 번째 수를 읽을 때 마다 구한 중앙값을 차례대로 공백으로 구분하여 출력한다. 이때, 한 줄에 10개씩 출력해야 한다.

접근 방식

1. 검색해보고 이해한 해는 우선순위 큐를 두개를 이용한 방식이다.

2. 찾아본 대략적인 구성은 중앙값 변수를 잡고
   중앙값보다 큰 값들의 minheap을 사용하는 우선순위큐,
   중앙값보다 작은 값들의 maxheap을 사용하는 우선순위 큐
   이렇게 3개로 이뤄져 있다.

3. 그 후 값이 들어올 때 마다 중앙값과 왼쪽 오른쪽 큐를 조절하며
   두 큐의 사이즈를 같거나 1만큼 차이나게 유지한다.
   밑의 코드에서는 ReAdjustQueue함수를 이용해 조절했다.

   /// <summary>
   /// 매개변수로 들어온 값을 넣으면서 leftMaxPq, rightMinPq큐내부와 median값 재조정
   /// </summary>
   /// <param name="elem(새로 들어온 값)"></param>
   /// <param name="order(elem의 index)"></param>
   void ReAdjustQueue(int elem,int order) {

4. 값이 들어올때 고려할 경우는 이번에 들어오는 값이

   • 홀수번째인지 짝수번째인지 생각
     ->홀수번째 들어오는 값이라면 왼쪽, 오른쪽 큐의 사이즈가 1만큼 차이남.
     -> 짝수번째 들어오는 값이라면 왼쪽, 오른쪽 큐의 사이즈가 같음.
   • 값이 중앙값과 같은 지
   • 값이 왼쪽 큐의 top보다 작은 지
   • 값이 왼쪽 큐의 top과 중앙값 사이인지
   • 값이 오른쪽 큐의 top과 중앙값 사이인지
   • 값이 오른쪽의 큐보다 큰지

   이정도로 나눠서 생각을 했다.

전체 코드

#include<iostream>
#include<queue>

using namespace std;
//왼쪽엔 max큐
priority_queue <int, vector<int>, less<int>>  leftMaxPq;
//오른쪽엔 min큐
priority_queue <int, vector<int>, greater<int>>  rightMinPq;

vector<int> ans;
//testcase수, 각 테케의 원소의 갯수, 각 원소입력받을 값, 중앙값
int T = 0, M = 0, tmp = 0, median = 0;

/// <summary>
/// 각 테스트케이스에서 사용하기 위해 초기화용 함수
/// </summary>
void Init() {
	median = 0;
	ans.clear();
	while (!leftMaxPq.empty()) {
		leftMaxPq.pop();
	}
	while (!rightMinPq.empty()) {
		rightMinPq.pop();
	}
}
/// <summary>
/// 매개변수로 들어온 값을 넣으면서 leftMaxPq, rightMinPq큐내부와 median값 재조정
/// </summary>
/// <param name="elem(새로 들어온 값)"></param>
/// <param name="order(elem의 index)"></param>
void ReAdjustQueue(int elem,int order) {
	//맨처음 값이 들어왔을 때,
	if (order == 1) {
		//중앙값에 값 넣기
		median = elem;
		return;
	}
	else if (order == 2) {
		if (median >= elem) leftMaxPq.push(elem);
		else rightMinPq.push(elem);
		return;
	}
	//3번째 값이 들어왔을땐 큐가 하나만 비어있는 상황
	else if (order == 3) {
		//leftMaxPq가 비어있을 때
		if (leftMaxPq.empty()) {
			//elem값이 median값보다 작거나 같을 때
			if (elem <= median) {
				leftMaxPq.push(elem);
				return;
			}
			//elem값이 rightminpq.top보다 작거나 같을 때
			else if (elem <= rightMinPq.top()) {
				leftMaxPq.push(median);
				median = elem;
				return;
			}
			//elem값이 rightminpq.top값보다 클때
			else {
				leftMaxPq.push(median);
				median = rightMinPq.top();
				rightMinPq.pop();
				rightMinPq.push(elem);
				return;
			}
		}
		//rightMinPq가 비어있을 때
		else {
			//중앙값보다 크거나 같으면
			if (median <= elem) {
				rightMinPq.push(elem);
				return;
			}
			//원소가 왼쪽 top값 보다 같거나 크면
			else if (elem >=leftMaxPq.top()) {
				rightMinPq.push(median);
				median = elem;
				return;
			}
			//원소가 왼쪽top값 보다 작으면
			else {
				rightMinPq.push(median);
				median = leftMaxPq.top();
				leftMaxPq.pop();
				leftMaxPq.push(elem);
				return;
			}
		}
	}

	//order가 짝수일 때 경우
	if (order % 2 == 0) {
		//중앙값과 같다면 
		if (elem == median) {
			//왼쪽으로 푸시
			leftMaxPq.push(median);
			return;
		}
		//elem이 median보다 크고 rightminpq.top보다 작을때
		else if (elem>median && elem<=rightMinPq.top()) {
			leftMaxPq.push(median);
			median = elem;
			return;
		}
		//elem이 median보다 작고 leftmaxpq.top보다 클때
		else if (elem<median && elem>=leftMaxPq.top()) {
			leftMaxPq.push(elem);
			return;
		}
		//elem이 rightMinpq.top보다 클때
		else if (elem>rightMinPq.top()) {
			rightMinPq.push(elem);
			return;
		}
		//elem이 leftmaxpq.top보다 작을 때
		else if(elem<leftMaxPq.top()) {
			leftMaxPq.push(elem);
			return;
		}
	}
	//순서가 홀수일 때, 두 큐의 사이즈는 1차이로 다름
	else {
		//왼쪽 큐 사이즈가 더 작다면
		if (leftMaxPq.size() < rightMinPq.size()) {
			//elem이 median값과 같다면 
			if (elem == median) {
				//오른쪽 큐에 median값 넣어줘서 큐 사이즈 동일하게 만듬
				leftMaxPq.push(elem);
				return;
			}
			//중앙값보단 크면서 오른쪽 top보다 작을 때
			else if (elem > median && elem <= rightMinPq.top()) {
				leftMaxPq.push(median);
				median = elem;
				return;
			}
			//중앙값보다 elem이 작으면(왼쪽큐top과 중앙값 사이일때나 왼쪽큐top보다 작을때나 똑같이 작동)
			else if (elem < median) {
				//그냥 바로 leftMaxpq에 푸시 
				leftMaxPq.push(elem);
				return;
			}
			//오른쪽 큐 top보다 크면 
			else if (elem > rightMinPq.top()) {
				leftMaxPq.push(median);
				median = rightMinPq.top();
				rightMinPq.pop();
				rightMinPq.push(elem);
				return;
			}
		}
		//오른쪽 큐의 사이즈가 더 작을땐 
		else {
			//중앙값과 같을 때
			if (median == elem) {
				rightMinPq.push(median);
				return;
			}
			//중앙값보다 클때(중앙값과 오른쪽 큐 top사이일때나 오른쪽큐 top보다 클때나 똑같이 작동)
			else if (median < elem) {
				rightMinPq.push(elem);
				return;
			}
			//중앙값과 왼쪽 큐의 top값 사이일때
			else if (elem < median && elem >= leftMaxPq.top()) {
				rightMinPq.push(median);
				median = elem;
				return;
			}
			//왼쪽값보다 작을 때
			else if (elem < leftMaxPq.top()) {
				rightMinPq.push(median);
				median = leftMaxPq.top();
				leftMaxPq.pop();
				leftMaxPq.push(elem);
				return;
			}

		}
	}
}

void Input() {
	cin >> T;
	for (int i = 0; i < T; i++) {
		cin >> M;
		Init();
		for (int j = 1; j <= M;j++ ) {
			cin >> tmp;
			ReAdjustQueue(tmp, j);
			//홀수번째라면
			if (j % 2) {
				//중앙값 ans에 넣어주기
				ans.push_back(median);
			}
		}
		//벡터 사이즈 출력
		cout << ans.size()<<'\n';
		//10개마다 줄바꿈해야해서 줄바꿈 체크용
		int cnt = 1;
		for (int elem : ans) {
			cout << elem << " ";
			//10개출력마다 줄 바꿈
			if (cnt % 10 == 0)
				cout << '\n';
			cnt++;
		}
		cout << '\n';
	}
}

int main() {
	Input();
}

문풀후생

우선순위큐의 효용성을 깨달은 문제다.

이전 문제인 백준2014: 소수의 곱 문제 처럼
어차피 제일 작은값이나 큰 값만 반환하게 되므로 나머지 값들은 신경쓰지 않는 부분이 제일 용이한 것 같다.

또한 중앙값의 왼쪽 오른쪽값들을 우선순위 큐 두개를 이용해 관리하는 구조를 보고 굉장히 많이 배웠다. 이렇게 활용할 수 있다니 감동.

또한 쌩으로 다 조건 나눠서 구현하다보니 예전에 스택을 이용한 계산기 구현할때 생각이 났다.
점점 조건을 계속 쪼개면서 드는 아 이거 조건 하나라도 빼먹으면 어떡하지 진짜 다시 보기싫다 이런 마음들
결국 이겨내고 구현하였다.