[C++] 백준 1655번 가운데를 말해요

 

1) 문제설명

백준 Online Judge 1655번 가운데를 말해요

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

1655번: 가운데를 말해요

 

2) 아이디어

우선순위 큐의 최대 힙과 최소 힙을 둘 다 사용하여 가운데 값을 구해야 한다.

1. 홀수번째 수 일 경우 최대 힙에 값을 넣고

2. 짝수번째 수 일 경우 최소 힙에 값을 넣는다.

3. 최대 힙의 최댓값이 최소 힙의 최솟값보다 작을 경우 두 원소를 바꿔준다. 

 

3) 코드

실패한 코드 : 시간 초과

#include<iostream>
#include<queue>
#include<deque>
#include<string.h>
#include<math.h>
#include<cmath>
#include<stack>
#include<algorithm>

using namespace std;

int cnt = 0;
int flag = 1;

int main() {
	int n;
	int arr[200001];
	priority_queue <int,vector<int>,greater<int>> pq;
	priority_queue <int, vector<int>, greater<int>> pq2;
	queue<int> q;
	cin >> n;
	for (int i = 1; i <= n; i++) {
		int a;
		cin >> a;
		pq.push(a);
		if (i >= 3) {
			int temp = pq.size();
			while (cnt < temp/2) {
				if (temp % 2 == 0 && flag == 1) {
					cnt = 1;
					flag = 0;
				}
				cnt++;	
				arr[cnt] = pq.top();
				pq.pop();
				
			}
			cout << pq.top() << endl;
			
			while (cnt > 0) { // 1
				
				pq.push(arr[cnt]);
				cnt--;
			}
		}
		cnt = 0;


		if (i < 3) {
			cout << pq.top() << endl;
		}
		
	}
}

 

성공한 코드

#include<iostream>
#include<queue>
#include<deque>
#include<string.h>
#include<math.h>
#include<cmath>
#include<stack>
#include<algorithm>

using namespace std;

int cnt = 1;
int flag = 1;

int main() {
	int n;
	int arr[200001];
	priority_queue <int,vector<int>,greater<int>> minheap; // 오름차순 2
	priority_queue <int, vector<int>, less <int >> maxheap; // 내림차순 3 , 1
	cin >> n;
	while (n--) {
		int a;
		scanf("%d", &a);
		cnt++;
		if (cnt % 2 == 1) {
			minheap.push(a);
		}
		else {
			maxheap.push(a);
		}
		if (cnt >= 3) {
			if (minheap.top() <= maxheap.top()) {
				int temp1 = minheap.top();
				int temp2 = maxheap.top();

				minheap.pop();
				maxheap.pop();

				minheap.push(temp2);
				maxheap.push(temp1);

			}
		}
		

		printf("%d\n", maxheap.top());
	}
}