BOJ 14427 : 수열과 쿼리 15 (Reference)

삼성 B형 전체 링크

 

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

 

 

B형에서는 Reference로 우선순위 큐 code가 주어진다.

하지만 STL(priority_queue) 사용이 가능하더라도, 갱신이 가능한 우선순위 큐는 직접 만들어야 한다.

여기서는 Reference 우선순위 큐로 문제를 풀었다. (Indexed Priority Queue, Heap)

 

해설은 이전 글을 참고하자.

#include <stdio.h>

int N, M;

typedef struct st
{
	int value;
	int id;
}HEAP;

HEAP heap[100100];
int heapIdx[100100];
int heapSize;

int isMin(HEAP a, HEAP b)
{
	if (a.value < b.value) return 1;
	else if (a.value == b.value)
	{
		if (a.id < b.id) return 1;
	}

	return 0;
}

int heapPush(HEAP* heap, int& heapSize, HEAP value, int* heapIdx) /* int -> HEAP */
{
	heap[heapSize] = value;
	heapIdx[value.id] = heapSize; /* index 저장 */

	int current = heapSize;
	while (current > 0 && isMin(heap[current], heap[(current - 1) / 2])) /* 우선순위 변경 */
	{
		HEAP temp = heap[(current - 1) / 2]; /* int -> HEAP */
		heap[(current - 1) / 2] = heap[current];
		heap[current] = temp;

		heapIdx[heap[current].id] = current; /* index 교환 */
		heapIdx[heap[(current - 1) / 2].id] = (current - 1) / 2;

		current = (current - 1) / 2;
	}

	heapSize = heapSize + 1;

	return 1;
}

int heapPop(HEAP* heap, int& heapSize, HEAP *value, int* heapIdx) /* int -> HEAP */
{
	*value = heap[0];
	heapSize = heapSize - 1;

	heap[0] = heap[heapSize];

	int current = 0;
	while (current * 2 + 1 < heapSize)
	{
		int child;
		if (current * 2 + 2 == heapSize)
		{
			child = current * 2 + 1;
		}
		else
		{
			child = /* 우선순위 변경 */
			  isMin(heap[current * 2 + 1], heap[current * 2 + 2]) ? current * 2 + 1 : current * 2 + 2;
		}

		if (isMin(heap[current], heap[child])) /* 우선순위 변경 */
		{
			break;
		}

		HEAP temp = heap[current]; /* int -> HEAP */
		heap[current] = heap[child];
		heap[child] = temp;

		heapIdx[heap[current].id] = current; /* index 교환 */
		heapIdx[heap[child].id] = child;

		current = child;
	}
	return 1;
}

void update(HEAP* heap, int& heapSize, int id, int* heapIdx, int value)
{
	int current = heapIdx[id];

	heap[current].value = value;

	while (current > 0 && isMin(heap[current], heap[(current - 1) / 2]))
	{
		HEAP temp = heap[(current - 1) / 2];
		heap[(current - 1) / 2] = heap[current];
		heap[current] = temp;

		heapIdx[heap[current].id] = current;
		heapIdx[heap[(current - 1) / 2].id] = (current - 1) / 2;

		current = (current - 1) / 2;
	}

	/* 아래로 내려가는 경우는 불필요 */

	while (current * 2 + 1 < heapSize)
	{
		int child;
		if (current * 2 + 2 == heapSize)
		{
			child = current * 2 + 1;
		}
		else
		{
			child = /* 우선순위 변경 */
			  isMin(heap[current * 2 + 1], heap[current * 2 + 2]) ? current * 2 + 1 : current * 2 + 2;
		}

		if (isMin(heap[current], heap[child])) /* 우선순위 변경 */
		{
			break;
		}

		HEAP temp = heap[current]; /* int -> HEAP */
		heap[current] = heap[child];
		heap[child] = temp;

		heapIdx[heap[current].id] = current; /* index 교환 */
		heapIdx[heap[child].id] = child;

		current = child;
	}
}

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

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

		HEAP tmp;
		tmp.value = a;
		tmp.id = i;

		heapPush(heap, heapSize, tmp, heapIdx);
	}

	scanf("%d", &M);
	for (int i = 0; i < M; i++)
	{
		int cmd;
		scanf("%d", &cmd);

		if (cmd == 1)
		{
			int Ai, v;

			scanf("%d %d", &Ai, &v);
			update(heap, heapSize, Ai, heapIdx, v);
		}
		else /* cmd == 2 */
			printf("%d\n", heap[0].id); /* reference의 경우 heap[0]이 가장 우선순위가 높다. */
	}

	return 0;
}

---

B형 reference에서 주어지는 우선순위 큐는 heap[0]이 가장 우선순위가 높은 값이다.