BOJ 7662 : 이중 우선순위 큐

삼성 B형 전체 링크

 

www.acmicpc.net/problem/7662

 

참고

- 우선순위 큐 Priority Queue

- 우선순위 큐 응용 (1) - 두 개의 heap을 이용하여 중앙값 찾기

- 우선순위 큐 응용 (2) - 최댓값, 최솟값 동시에 관리하기

- 우선순위 큐 임의 원소 삭제

- 우선순위 큐 임의 원소 삭제 최적화

- 우선순위 큐 임의 원소 갱신, 변경

 

 

가운데를 말해요에서 최대힙과 최소힙 두 개를 이용하여 중앙값을 유지시켰다.

 

이중 우선순위 큐도 마찬가지로 최대힙에서 최댓값을 관리하고 최소힙에서 최솟값을 관리하면

데이터의 최댓값과 최솟값을 O(1)만에 찾을 수 있다. (heap[1]로 접근하면 된다.)

그런데, 최소힙에서 삭제된 data를 최대힙에서 단순히 삭제할 수는 없다. (반대도 마찬가지)

따라서 data를 따로 저장하여, 그 data가 유효한지 check하는 방법을 사용한다.

 

해시 테이블의 데이터 삭제에서는 data는 따로 저장하고, pointer를 이용하여 그 data가 삭제되었는지 판단하였다.

이중 우선순위 큐에서는 pointer 대신 data의 index로 접근하는 방법으로 구현해보았다.

---

먼저 어떻게 최솟값과 최댓값을 동시에 관리할지 생각해보자.

 

1) 최솟값은 minHeap에 관리한다. 그러면 minHeap[1]이 최솟값이다.

2) 최댓값은 maxHeap에 관리한다. 그러면 maxHeap[1]이 최댓값이다.

 

여기까지는 당연한 얘기다.

그런데 이제 최댓값을 삭제하는 명령 D 1이 들어왔다고 생각해보자.

 

3) 최댓값은 maxHeap에서 pop한다. 

4) minHeap에서는 최댓값을 어떻게...?

 

하지만 minHeap에서 최댓값을 삭제할 수가 없다.

우선순위 큐의 임의 원소 삭제에서는 heap index를 메모해두는 방법으로 특정 값을 삭제할 수 있었지만,

여기에서는 정수의 범위가 32비트로 굉장히 넓어서 관리하기가 힘들다.

minHeap에 최댓값은 최악의 우선순위지만 heap의 특성상 반드시 마지막 hn에 저장되었을 거라는 보장도 없다.

 

하지만 minHeap에서 당장 삭제할 필요가 없다.

minHeap에서는 우선 최솟값만 pop이 되기 때문이다.

이때, pop이 된 data가 maxHeap에서 삭제되었었는지 확인할 수 있는 방법만 있으면 된다.

 

따라서 data 자체는 따로 관리하고, 그 data에 flag를 둬서 삭제 여부를 표시만 한다.

heap에는 dataIdx를 같이 추가해주면 된다.

typedef struct st1
{
	int value;
	int deleteFlag; /* data의 삭제 여부 */
}DATA;

DATA data[MAX];
int dcnt;

typedef struct st2
{
	int value;
	int dataIdx; /* data[]의 index */
}HEAP;

HEAP minHeap[MAX];
int minHn;

HEAP maxHeap[MAX];
int maxHn;

 

값이 들어올 때마다 data[dcnt].value에 값을 저장하고, deleteFlag = 0으로 해둔다.

최댓값을 삭제할 때, HEAP에 dcnt를 저장해두면, pop하였을 때 나온 원소로 data에 직접 접근이 가능하다.

pop하고 나서 data의 deleteFlag = 1로 해두면, minHeap에서 따로 지울 필요가 없다.

 

최댓값에서 data를 삭제할 때, data에 직접 접근해서 삭제 표시를 하였으므로,

minHeap에서 pop이 될 때, deleteFlag를 보고 삭제된 data를 구분할 수 있는 것이다.

while (data[minHeap[1].dataIdx].deleteFlag) minPop(minHeap, minHn);

위의 코드는 minHeap에서 우선순위가 높은 순서대로 delete된 data면 불필요하므로 pop하는 코드다.

 

minHeap[1]이 가장 작은 값이다.

그 가장 작은 값의 dataIdx로 data[dcnt]로 저장한 data에 바로 접근할 수 있다.

이 data의 deleteFlag = 1이면 minPop으로 minHeap[1]을 삭제한다. (maxHeap에서 삭제한 data이므로)

 

우선순위가 높은 minHeap[1]만 계속 삭제하면 된다. 뒷 부분의 heap은 더이상 삭제할 필요가 없다.

어짜피 minHeap에서 중요한 것은 최솟값이기 때문이다.

최솟값이 아닌 data는 나중에 우선순위가 높아질 때 삭제하면 된다.

 

여기서 문제는 data의 갯수를 기억해둬야 하는 것이다.

minHeap이나 maxHeap에서 pop하면 minHn과 maxHn은 줄어들지만,

maxHeap에서 삭제하였다고 minHeap의 minHn이 줄어들지는 않는다.

 

따라서 실제 data의 갯수인 dataCount 변수로 삭제되지 않은 data의 갯수를 따로 관리해야 한다.

코드로 확인해보자.

if (command == 'I') /* 삽입 명령 */
{
	data[dcnt].value = value;
	data[dcnt].deleteFlag = 0; /* tc가 여러 개이므로 초기화 */

	maxPush(maxHeap, maxHn, { value, dcnt });
	minPush(minHeap, minHn, { value, dcnt });
				
	dcnt++;
	dataCount++; /* 실제 data의 개수 */
}
else /* 삭제 명령 */
{ ... }

 

Insert 명령이 들어온 경우, 그 값을 data[dcnt]에 순서대로 입력한다.

이 dcnt를 max/min heap에 같이 push해둔다.

그리고 실제 dataCount도 같이 증가시킨다.

 

이제 삭제 명령을 보자.

if (command == 'I') /* 삽입 명령 */
{ ... }
else /* 삭제 명령 */
{
	if (dataCount == 0)
	{
		maxHn = minHn = 0;
		continue;
	}

	/* 우선순위가 높은 data가 삭제되었으면 불필요하므로 제거 */
	while (data[maxHeap[1].dataIdx].deleteFlag) maxPop(maxHeap, maxHn);
	while (data[minHeap[1].dataIdx].deleteFlag) minPop(minHeap, minHn);
				
	dataCount--; /* 실제 data의 개수 */

	HEAP tmp;
	if (value == 1) /* 최댓값 삭제 */
	{
		tmp = maxPop(maxHeap, maxHn);
		data[tmp.dataIdx].deleteFlag = 1;
	}
	else /* 최솟값 삭제 */
	{
		tmp = minPop(minHeap, minHn);
		data[tmp.dataIdx].deleteFlag = 1;
	}
}

 

data가 남아 있지 않으면 D 명령어를 무시하라고 하였으므로, continue를 이용한다.

이때, maxHn과 minHn으로 남은 data의 갯수를 세면 안된다.

서로의 heap에 삭제된 데이터는 여전히 남아있을 수 있기 때문에 실제 data의 갯수인 dataCount로 판단한다.

 

dataCount가 존재하는 경우, 각 heap에서 우선순위가 높은 data중 삭제된 data는 pop한다.

그리고 추가 명령(1, -1)에 의해 maxHeap이나 minHeap을 pop하고 data에 삭제 표시를 한다.

 

최종적으로 출력할 최댓값과 최솟값도 마찬가지로 불필요한 data를 pop하고, 한번 더 pop해서 출력한다.

if (dataCount)
{
	/* 우선순위가 높은 data가 삭제되었으면 불필요하므로 제거 */
	while (data[maxHeap[1].dataIdx].deleteFlag) maxPop(maxHeap, maxHn);
	while (data[minHeap[1].dataIdx].deleteFlag) minPop(minHeap, minHn);

	HEAP maxValue = maxPop(maxHeap, maxHn);
	HEAP minValue = minPop(minHeap, minHn);

	printf("%d %d\n", maxValue.value, minValue.value);
}
else
	printf("EMPTY\n");

 

최종 코드는 아래와 같다.

#include <stdio.h>

#define MAX (1000000 + 10000)

int T;

typedef struct st1
{
	int value;
	int deleteFlag;
}DATA;

DATA data[MAX];
int dcnt;

typedef struct st2
{
	int value;
	int dataIdx;
}HEAP;

HEAP minHeap[MAX];
int minHn;

HEAP maxHeap[MAX];
int maxHn;

HEAP maxPop(HEAP* heap, int& hn)
{
	HEAP tmp, ret;

	ret = heap[1];
	heap[1] = heap[hn];
	heap[hn--].value = 0x80000000; /* -2147483648 */

	for (int i = 1; i * 2 <= hn;)
	{
		if (heap[i].value > heap[i * 2].value && heap[i].value > heap[i * 2 + 1].value) break;
		else if (heap[i * 2].value > heap[i * 2 + 1].value)
		{
			tmp = heap[i * 2];
			heap[i * 2] = heap[i];
			heap[i] = tmp;

			i = i * 2;
		}
		else
		{
			tmp = heap[i * 2 + 1];
			heap[i * 2 + 1] = heap[i];
			heap[i] = tmp;

			i = i * 2 + 1;
		}
	}

	return ret;
}

void maxPush(HEAP* heap, int& hn, HEAP x)
{
	HEAP tmp;

	heap[++hn] = x;

	for (int i = hn; i > 1; i /= 2)
	{
		if (heap[i / 2].value > heap[i].value) break;

		tmp = heap[i / 2];
		heap[i / 2] = heap[i];
		heap[i] = tmp;
	}
}

HEAP minPop(HEAP* heap, int& hn)
{
	HEAP tmp, ret;

	ret = heap[1];
	heap[1] = heap[hn];
	heap[hn--].value = 0x7fffffff; /* 2147483647 */

	for (int i = 1; i * 2 <= hn;)
	{
		if (heap[i].value < heap[i * 2].value && heap[i].value < heap[i * 2 + 1].value) break;
		else if (heap[i * 2].value < heap[i * 2 + 1].value)
		{
			tmp = heap[i * 2];
			heap[i * 2] = heap[i];
			heap[i] = tmp;

			i = i * 2;
		}
		else
		{
			tmp = heap[i * 2 + 1];
			heap[i * 2 + 1] = heap[i];
			heap[i] = tmp;

			i = i * 2 + 1;
		}
	}

	return ret;
}

void minPush(HEAP* heap, int& hn, HEAP x)
{
	HEAP tmp;

	heap[++hn] = x;

	for (int i = hn; i > 1; i /= 2)
	{
		if (heap[i / 2].value < heap[i].value) break;

		tmp = heap[i / 2];
		heap[i / 2] = heap[i];
		heap[i] = tmp;
	}
}

int main(void)
{
	scanf("%d", &T);

	for (int tc = 0; tc < T; tc++)
	{
		int k, dataCount;
		
		scanf("%d", &k);

		/* data, heap, 실제 존재하는 data 초기화 */
		dcnt = minHn = maxHn = dataCount = 0;

		for (int i = 0; i < k; i++)
		{
			char command;
			int value;

			scanf(" %c %d", &command, &value);

			if (command == 'I') /* 삽입 명령 */
			{
				data[dcnt].value = value;
				data[dcnt].deleteFlag = 0; /* tc가 여러 개이므로 초기화 */

				maxPush(maxHeap, maxHn, { value, dcnt });
				minPush(minHeap, minHn, { value, dcnt });
				
				dcnt++;
				dataCount++;
			}
			else /* 삭제 명령 */
			{
				if (dataCount == 0)
				{
					maxHn = minHn = 0;
					continue;
				}

				/* 우선순위가 높은 data가 삭제되었으면 불필요하므로 제거 */
				while (data[maxHeap[1].dataIdx].deleteFlag) maxPop(maxHeap, maxHn);
				while (data[minHeap[1].dataIdx].deleteFlag) minPop(minHeap, minHn);
				
				dataCount--;

				HEAP tmp;
				if (value == 1) /* 최댓값 삭제 */
				{
					tmp = maxPop(maxHeap, maxHn);
					data[tmp.dataIdx].deleteFlag = 1;
				}
				else /* 최솟값 삭제 */
				{
					tmp = minPop(minHeap, minHn);
					data[tmp.dataIdx].deleteFlag = 1;
				}
			}
		}
		
		if (dataCount)
		{
			/* 우선순위가 높은 data가 삭제되었으면 불필요하므로 제거 */
			while (data[maxHeap[1].dataIdx].deleteFlag) maxPop(maxHeap, maxHn);
			while (data[minHeap[1].dataIdx].deleteFlag) minPop(minHeap, minHn);

			HEAP maxValue = maxPop(maxHeap, maxHn);
			HEAP minValue = minPop(minHeap, minHn);

			printf("%d %d\n", maxValue.value, minValue.value);
		}
		else
			printf("EMPTY\n");
	}

	return 0;
}

---

B형에서 중앙값, 최솟값, 최댓값을 동시에 관리해야할 때, 우선순위 큐를 이용해보자.