BOJ 1655 - 가운데를 말해요(C++)

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

1655번: 가운데를 말해요

 

풀이

우선순위 큐와 구역을 나누는 것으로 해결가능

  - 중간 값과 더 작은 값들을 저장하는 오름차순 우선 순위 큐 :  little_pq,

  - 중간 값보다 쿤 값들을 저장하는 내림차순 우선순위 큐 : big_pq

 

1. 상황에 따라 하나의 우선 순위 큐에 값을 저장

• 두개의 큐에 값이 없는 초기 상태거나 큐의 사이즈가 같다면 little_pq에 저장
  • 외친 수(현재까지의 수)가 짝수라면 중앙에 있는 두 수중 작은 수를 말해야해서
• little_pq의 크기가 big_pq의 크기보다 크다면 big_pq에 저장

2. 두개의 큐의 크기가 0보다 크고, little_pq의 top(최대값)이 big_pq의 top(최소값)보다 크면 교환

• little_pq의 top은 중앙 값인데 big_pq의 top(중앙값 이상의 수중 최소값)보다 클 수가 없기 때문에

3. little_pq의 top을 출력하고 다음 값에 대해 1로 이동

 

 

문제점

올바른 풀이로 풀었다고 생각해도 시간 초과가 발생 -> 입/출력의 시간 때문에

 

해결방법

• ios::sync_with_stdio(false);
• C와 C++의 표준 Stream 동기화를 끊는 것
• 기본적으로는 동기화 되어 있기때문에 C/C++의 입출력 방식을 자유롭게 혼용가능
• 사용하는 버퍼 수가 줄어 들기 때문에 실행속도가 향상
• cin:tie(NULL);
• cin과 cout의 묶음을 풀어주는 것
• 기본적으로 cin, cout은 묶여 있고 다른 I/O작업 진행 전에 자동으로 버퍼를 비워줌
• 이러한 처리 과정이 없기 때문에 실행속도가 향상

 

#include <iostream>
#include <queue>

using namespace std;

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

	int N;
	cin >> N;
	priority_queue<int> little_pq;
	priority_queue<int, vector<int>, greater<int>> big_pq;

	for (int i = 0; i < N; i++) {
		int temp;
		cin >> temp;


		if (little_pq.size() == big_pq.size()) {
			little_pq.push(temp);
		}
		else if (little_pq.size() > big_pq.size()) {
			big_pq.push(temp);
		}

		if ((little_pq.size()>0&& big_pq.size() > 0)&&(little_pq.top() > big_pq.top())) {
			int max_temp = little_pq.top();
			int min_temp = big_pq.top();
			little_pq.pop();
			big_pq.pop();
			big_pq.push(max_temp);
			little_pq.push(min_temp);
		}
		cout << little_pq.top() << endl;
	}
	return 0;
}