구조체 힙 - B형 Reference 코드 (우선순위 큐)

삼성 B형 전체 링크

 

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

코드 변경을 최소화해서 구조체 힙을 풀어보자.

---

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 부분을 isMin(A, B)로 변경하면 된다. (구조체 우선순위 비교 함수)

 

국영수 문제의 경우 우선순위는 아래와 같다.

int isMin(HEAP a, HEAP b) /* int -> HEAP */
{
	if (a.kr > b.kr) return 1;
	if (a.kr == b.kr)
	{
		if (a.en < b.en) return 1;

		if (a.en == b.en)
		{
			if (a.math > b.math) return 1;

			if (a.math == b.math)
			{
				if (mystrcmp(a.name, b.name) < 0) return 1;
			}
		}

	}

	return 0;
}

 

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

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

#include <stdio.h>

int N;

typedef struct st
{
	char name[15];
	int kr;
	int en;
	int math;
}HEAP;

HEAP heap[100100]; /* int -> HEAP */
int heapSize;

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;
}

int isMin(HEAP a, HEAP b) /* int -> HEAP */
{
	if (a.kr > b.kr) return 1;
	if (a.kr == b.kr)
	{
		if (a.en < b.en) return 1;

		if (a.en == b.en)
		{
			if (a.math > b.math) return 1;

			if (a.math == b.math)
			{
				if (mystrcmp(a.name, b.name) < 0) return 1;
			}
		}

	}

	return 0;
}

int heapPush(HEAP* heap, int& heapSize, HEAP value) /* int -> HEAP */
{
	heap[heapSize] = value;

	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;
		current = (current - 1) / 2;
	}

	heapSize = heapSize + 1;

	return 1;
}

int heapPop(HEAP* heap, int& heapSize, HEAP *value) /* 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;

		current = child;
	}
	return 1;
}

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

	for (int i = 0; i < N; i++)
	{
		HEAP x;
		int kr, en, math;
		char str[15];

		scanf("%s %d %d %d", str, &kr, &en, &math);

		x.kr = kr;
		x.en = en;
		x.math = math;
		mystrcpy(x.name, str);

		heapPush(heap, heapSize, x);
	}

	for (int i = 0; i < N; i++)
	{
		HEAP tmp;
		heapPop(heap, heapSize, &tmp);
		printf("%s\n", tmp.name);
	}

	return 0;
}

---

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