우선순위 큐 갱신 - B형 Reference 코드

삼성 B형 전체 링크

 

B형 reference 코드의 우선순위 큐는 최소 힙만 주어져있다.

 

이번에는 우선순위 큐의 갱신을 알아보자. (Indexed Priority Queue, Heap)

(삭제의 경우는 갱신 후 pop을 하면 되므로 필요시 적절히 코드를 수정하자.)

 

풀어볼 문제는 BOJ : 20920 영단어 암기는 괴로워이다.

---

reference 코드에서 우선순위를 비교하는 곳을 구조체에 대한 우선순위로 수정한다.

 

1) heapPush의

    while (current > 0 && heap[current] < heap[(current - 1) / 2])

 

2) heapPop의 

    child =
        heap[current * 2 + 1] < heap[current * 2 + 2] ? current * 2 + 1 : current * 2 + 2;

 

3) heapPop의

    if (heap[current] < heap[child])
    {
        break;
    }

 

A < B 부분을 isPriority(A, B)로 변경하면 된다. (구조체 우선순위 비교 함수)

 

영단어 암기는 괴로워 문제의 경우 우선순위는 아래와 같다.

int mystrcmp(const char *a, const char *b)
{
	while (*a && *a == *b) ++a, ++b;
	return *a - *b;
}

int isPriority(HEAP a, HEAP b)
{
	if (a.count > b.count) return 1;
	else if (a.count == b.count && a.length > b.length) return 1;
	else if (a.count == b.count && a.length == b.length && mystrcmp(a.word, b.word) < 0) return 1;

	return 0;
}

 

그리고 모든 heap의 type int에 대해 구조체 type HEAP으로 변경해주면 된다.

함수에 넘겨주는 heap, 교체에 필요한 temp 모두 HEAP으로 변경하였다.

 

heapPush/Pop에 heapIdx를 넘겨주고, 갱신하는 코드를 추가한다.

heapPush에서는 index를 저장하고 교환, heapPop에서는 교환만 한다. (주석 참고)

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 && isPriority(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 = /* 우선순위 변경 */
			 isPriority(heap[current * 2 + 1], heap[current * 2 + 2]) ? current * 2 + 1 : current * 2 + 2;
		}

		if (isPriority(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;
}

 

 

그리고 update 함수를 추가한다.

update에서 id를 넘겨 받으면, heap에 바로 접근하여 값을 수정할 수 있다.

수정 된 값은 heapPush/Pop의 방법으로 갱신된다.

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

	heap[current].count++;

	/* heapPush 응용 */
	while (current > 0 && isPriority(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;
	}

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

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

		if (isPriority(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;
	}
}

이 문제의 경우 단어의 수만 heap에 바로 접근하여 단어의 수(count)를 증가시키고 갱신하였다.

 

단어의 수는 항상 증가하기 때문에 heap이 아래로 내려가지 않으므로, return하였다.

(참고용으로만 남겨두었다.)

 

최종 코드는 아래와 같다.

#include <stdio.h>

#define MAX (100000 + 1000)
#define MAX_TABLE (200009)

typedef unsigned long long int ull;

int N, M;

typedef struct st1
{
	int id;
	char word[11];
	struct st1 *next;
}HASH;

HASH HASH_TABLE[MAX_TABLE];
HASH POOL[MAX];
int pcnt;

typedef struct st2
{
	int count;
	int length;
	char* word;
	int id;
}HEAP;

HEAP heap[MAX];
int heapIdx[MAX]; /* id가 heap의 어느 위치에 있는지 저장할 배열 */
int heapSize;

int mystrlen(char * str)
{
	int len = 0;

	while (*str++) len++;

	return len;
}

void mystrcpy(char *a, const char *b)
{
	while (*a++ = *b++);
}

int mystrcmp(const char *a, const char *b)
{
	while (*a && *a == *b) ++a, ++b;
	return *a - *b;
}

ull hash(const char *str)
{
	ull hash = 5381;
	int c;

	while (c = *str++)
	{
		hash = (((hash << 5) + hash) + c) % MAX_TABLE;
	}

	return hash % MAX_TABLE;
}

int isPriority(HEAP a, HEAP b)
{
	if (a.count > b.count) return 1;
	else if (a.count == b.count && a.length > b.length) return 1;
	else if (a.count == b.count && a.length == b.length && mystrcmp(a.word, b.word) < 0) 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 && isPriority(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 = /* 우선순위 변경 */
			 isPriority(heap[current * 2 + 1], heap[current * 2 + 2]) ? current * 2 + 1 : current * 2 + 2;
		}

		if (isPriority(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 current = heapIdx[id];

	heap[current].count++;

	/* heapPush 응용 */
	while (current > 0 && isPriority(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;
	}

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

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

		if (isPriority(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 checkExist(char* word, ull h)
{
	HASH *nd = HASH_TABLE[h].next;

	while (nd)
	{
		if (!mystrcmp(nd->word, word)) return nd->id;
		nd = nd->next;
	}

	return 0;
}

int main(void)
{
	int id;
	char str[11];

	scanf("%d %d", &N, &M);

	id = 1;
	for (int i = 0; i < N; i++)
	{
		scanf("%s", str);

		int length = mystrlen(str);
		if (length < M) continue;

		ull h = hash(str);
		int checkId = checkExist(str, h);

		if (checkId) update(heap, heapSize, checkId, heapIdx);
		else
		{
			HASH *nd = &POOL[pcnt++];

			nd->id = id; /* id 는 1부터 시작 */
			mystrcpy(nd->word, str);

			nd->next = HASH_TABLE[h].next;
			HASH_TABLE[h].next = nd; /* name에 해당하는 key에 연결 */

			HEAP dic = { 0 };

			dic.count = 1; /* 최초 count는 1 */
			dic.length = length;
			dic.word = nd->word; /* pointer로 HASH의 word를 가르키기만 한다. */
			dic.id = id++;

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

	while (heapSize)
	{
		HEAP dic;
		heapPop(heap, heapSize, &dic, heapIdx);
		printf("%s\n", dic.word);
	}

	return 0;
}

---

실제 시험에서는 register도 추가해주자.