대엉코딩

www.acmicpc.net/problem/1655

1. 풀이방법

 - 직관적인 풀이 : 중간값을 의미를 떠올리면 수빈이가 숫자를 하나 외칠 때 마다 정렬을 수행 후 중간에 위치한

                        값을 뽑아내면 된다 . ---> 시간초과 (아마? 작성해서 제출해보진 않았습니다.)

 - 우선순위 큐를 이용했습니다.

   (1단계)

      -가장 큰 값을 뽑아내는 pqless와 가장 작은 값을 뽑아내는 pqgreater를 선언 후 

      - 매 단계 마다, 그 전의 중간값을 기준으로 pqless에 넣을지 pqgreater에 넣을지를 판단해서 우선순위 큐에 삽입

   (2단계)

      - 중간값을 뽑아내기 위해서는 한쪽 우선순위 큐만 너무 커져 버리면 안됩니다 즉 데이터의 수가 1차이 이하로 나야

         하므로 2이상 차이가 날경우 큰 쪽의 우선순위 큐의 값을 작은 크기의 우선순위 큐 로 옮겨주는 작업을 수행

   (3단계)

      - 중간값을 뽑아내서 출력 (다음단계를 위한 중간값 저장)

      - 문제 조건에 따라서 두 우선순위큐의 사이즈를 비교한후 (편의상) 왼쪽 위에 뽑아낼지 오른쪽 위에서 뽑아낼지

         결정하면 됩니다.

2. 주의사항

 - 개인적으로는 우선순위 큐 두개를 사용해야 겠다 라는 생각이 든 이후 부터는 상대적으로 매우 쉬웠습니다.

 - 문제 조건에 따른 단계별 구현만 차근차근 해주시면 되겠습니다.

3. 나의코드

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

int N;
int centervalue;

priority_queue<int, vector<int>> pqless;
priority_queue<int, vector<int>, greater<int>> pqgreater;

void InputToQueue(int num) {
	if (num <= centervalue) { pqless.push(num); }
	else { pqgreater.push(num); }
}
void ModifyQueue() {
	if (pqless.size() > pqgreater.size() + 1) { //2이상 차이날 경우
		int modinum = pqless.top();
		pqless.pop();
		pqgreater.push(modinum);
	}
	else if (pqgreater.size() > pqless.size() + 1) { //2이상 차이날 경우
		int modinum = pqgreater.top();
		pqgreater.pop();
		pqless.push(modinum);
	}
}
void GetCenterValue() {
	if (pqless.size() >= pqgreater.size()) {
		centervalue = pqless.top();
	}
	else {
		centervalue = pqgreater.top();
	}
	cout << centervalue << "\n";
}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	cin >> N;
	int tmp;
	for (int i = 0; i < N; i++) {
		cin >> tmp;
		if (i == 0) {
			pqless.push(tmp); centervalue = tmp; cout << centervalue << "\n"; continue;
		}
		InputToQueue(tmp);
		ModifyQueue();
		GetCenterValue();
	}
	return 0;
}