백준 1655 가운데를 말해요

 

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

 

서론

상당히 오래 걸린 문제. 반나절은 푼것 같다.

우선순위 큐는 내부 힙이 완벽히 정렬이 되지는 않지만 큐에서 빼낼때마다 배열에 저장하면 완벽히 정렬이 된다.

그래서 입력 한번 받을때마다 큐를 비웠다 채웠다를 반복해봤는데 시간초과

트리에서 수식으로 얻을 수 있는게 있는지 고민해봤으나 찾을 수 없었다.

엑셀에서 예상되는 결과를 표로 그려봤는데 시프트레지스터가 떠올라서 아이디어를 얻을 수 있었다.

 

아이디어

 

 

입력값이 들어올때마다 예상되는 중앙값을 표로 나타내봤다.

각 행의 노란색 셀이 중앙값인데, 노란색 셀이 두개면 둘 중 최소값이다.

우선순위 큐에선 입력될때마다 위와 같이 완벽히 정렬이 되지는 않지만 일단은 정렬이 된다고 가정하고

우선순위 큐를 사용하라고 하니 우선순위 큐의 루트가 중앙값이 오도록 어떻게든 만들어 내야 한다.

 

위의 표의 특이점은 중앙값을 중심으로 좌측은 중앙값보다 작은 값들이 오름차순으로 정렬되어있고

우측은 중앙값보다 큰 값들이 오름차순으로 정렬되어 있단거다.

즉 중앙값의 한칸 왼쪽 값은 중앙값보다 작지만 왼쪽 값들 중 가장 큰 값(=최대 힙)이고

한칸 오른쪽 값은 중앙값보다 크지만 오른쪽 값들 중 가장 작은 값(=최소 힙)이다.

 

따라서 중앙값을 중심으로 좌측에 최대힙을 가지는 우선순위 큐를, 우측에 최소힙을 가지는 우선순위 큐를 만들어주면 된다.

 

 

그래서 만들어야 하는 결과를 우선 만들었다.

중앙값은 각 큐의 루트 힙 중 하나인데, 입력개수가 홀수면 오른쪽 큐의 루트 힙을 중앙값으로 잡았다. 

일단 첫 입력값은 무조건 오른쪽 큐에 넣고

두번째 입력값부턴 오른쪽 큐의 최소 힙보다 작으면 왼쪽 큐에, 아니면 오른쪽 큐에 넣는다.

그런데 한쪽 큐에만 새로운 값이 계속 들어오면 각 큐들의 사이즈가 비대칭이 되어 각 큐의 루트 힙이 중앙값이 될 수 없다. 루트 힙이 중앙값이 되려면 왼쪽, 오른쪽 큐의 입력개수를 동일하게 만들어줘야한다.

단 총 입력 개수가 홀수일때는 오른쪽 큐의 루트가 중앙값이라 오른쪽 큐는 왼쪽 큐보다 하나 많다.

각 큐 사이즈를 대칭으로 만들기 위해서는 한칸씩 시프트 시켜주면 된다.

왼쪽 큐 사이즈가 오른쪽 큐보다 많다면 왼쪽 큐에서 빼낸 값을 오른쪽 큐에 넣어준다.

 

구현

//c++

#pragma warning(disable : 4996)
#include <cstdio>
#include <iostream>
#include <queue>
#include <algorithm>

int main() {
	std::priority_queue<int, std::vector<int>, std::less<int>> qLeft;
	std::priority_queue<int, std::vector<int>, std::greater<int>> qRight;

	int n;
	scanf("%d", &n);

	for (int i = 1; i <= n; i++) {
		int x;
		scanf("%d", &x);

		if (i == 1) qRight.push(x); 
		else if (x < qRight.top()) qLeft.push(x);
		else qRight.push(x);

		if (qRight.size() >= qLeft.size() + 2) { // 왼쪽 시프트
			qLeft.push(qRight.top());
			qRight.pop();
		}
		else if (qLeft.size() >= qRight.size() + 1) { // 오른쪽 시프트
			qRight.push(qLeft.top());
			qLeft.pop();
		}

		if (qRight.size() == qLeft.size()) printf("%d\n", std::min(qLeft.top(), qRight.top()));
		else printf("%d\n", qRight.top());
	}
}

 

시간초과 풀이

//c++

#pragma warning(disable : 4996)
#include <cstdio>
#include <iostream>
#include <queue>
#include <algorithm>

int main() {
	std::priority_queue<int> pq;
	std::priority_queue<int> pq2;
	int n;
	scanf("%d", &n);

	for (int i = 1; i <= n; i++) {
		int x;
		scanf("%d", &x);
		pq.push(x);
		
		for (int j = 0; j < i / 2; j++) {
			pq2.push(pq.top());
			pq.pop();
		}
		int mid1 = pq.top();
		int mid2 = 0;
		if (i != 1) mid2 = pq2.top();

		for (int j = 0; j < i / 2; j++) {
			pq.push(pq2.top());
			pq2.pop();
		}
		if (i % 2 == 0) printf("%d\n", std::min(mid1, mid2));
		else printf("%d\n", mid1);
	}
}