[Algorithm][C++] BOJ 10825: 국영수 (Priority Queue, Heap)

url: https://www.acmicpc.net/problem/10825

10825번: 국영수

 

풀이 핵심

1. 삼성 B형 대비 우선 순위 큐 (Priority Queue, Heap) 자료구조를 이용해 문제를 풀어보자

(Min Heap으로 대략적인 개념 잡기)

 

2. 이름, 국/영/수 성적을 담을 구조체와 data를 pool 할 수 있는 datapool, heap을 다음과 같이 만든다.

struct Database {
	char name[11];
	int ko, eng, math;
};
Database dataPool[MAXN];
int pcnt; // memory pool count

Database* heap[MAXN];
int hSize; // heap size

 

3. 가장 중요한 비교 함수 (comp), heapPush, heapPop 함수를 다음과 같이 구성한다. (strcmp, strcpy는 필수!!)

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 comp(Database* a, Database* b) {
	if (a->ko == b->ko) {
		if (a->eng == b->eng) {
			if (a->math == b->math) {
				return mystrcmp(a->name, b->name);
			}
			return b->math - a->math;
		}
		return a->eng - b->eng;
	}
	return b->ko - a->ko;
}

void heapPush(const char* name, int ko, int eng, int math) {
	if (hSize == MAXN - 1) return;
	Database* db = &dataPool[pcnt++];
	mystrcpy(db->name, name);
	db->ko = ko, db->eng = eng, db->math = math;
	heap[++hSize] = db;
	int current = hSize;
	int parent = current / 2;

	while (parent > 0) {
		if (comp(heap[current], heap[parent]) > 0) break;
		Database* temp = heap[current];
		heap[current] = heap[parent];
		heap[parent] = temp;

		current = parent;
		parent = current / 2;
	}
}

Database* heapPop() {
	if (hSize == 0) return 0;
	Database* ret = heap[1];
	heap[1] = heap[hSize--];
	int current = 1, leftChild = 2, rightChild = 3, child;

	while (leftChild <= hSize) {
		if (leftChild == hSize) child = leftChild;
		else child = (comp(heap[leftChild], heap[rightChild]) < 0) ? leftChild : rightChild;
		if (comp(heap[current], heap[child]) < 0) break;
		Database* temp = heap[current];
		heap[current] = heap[child];
		heap[child] = temp;

		current = child;
		leftChild = current * 2;
		rightChild = leftChild + 1;
	}
	return ret;
}

 

 

전체 코드

#include <cstdio>
#define MAXN	100001

struct Database {
	char name[11];
	int ko, eng, math;
};
Database dataPool[MAXN];
int pcnt;

Database* heap[MAXN];
int hSize;

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 comp(Database* a, Database* b) {
	if (a->ko == b->ko) {
		if (a->eng == b->eng) {
			if (a->math == b->math) {
				return mystrcmp(a->name, b->name);
			}
			return b->math - a->math;
		}
		return a->eng - b->eng;
	}
	return b->ko - a->ko;
}

void heapPush(const char* name, int ko, int eng, int math) {
	if (hSize == MAXN - 1) return;
	Database* db = &dataPool[pcnt++];
	mystrcpy(db->name, name);
	db->ko = ko, db->eng = eng, db->math = math;
	heap[++hSize] = db;
	int current = hSize;
	int parent = current / 2;

	while (parent > 0) {
		if (comp(heap[current], heap[parent]) > 0) break;
		Database* temp = heap[current];
		heap[current] = heap[parent];
		heap[parent] = temp;

		current = parent;
		parent = current / 2;
	}
}

Database* heapPop() {
	if (hSize == 0) return 0;
	Database* ret = heap[1];
	heap[1] = heap[hSize--];
	int current = 1, leftChild = 2, rightChild = 3, child;

	while (leftChild <= hSize) {
		if (leftChild == hSize) child = leftChild;
		else child = (comp(heap[leftChild], heap[rightChild]) < 0) ? leftChild : rightChild;
		if (comp(heap[current], heap[child]) < 0) break;
		Database* temp = heap[current];
		heap[current] = heap[child];
		heap[child] = temp;

		current = child;
		leftChild = current * 2;
		rightChild = leftChild + 1;
	}
	return ret;
}

int main() {
	int N;
	char name[11];
	int ko, eng, math;
	scanf("%d", &N);
	for (int i = 0; i < N; i++) {
		scanf("%s %d %d %d", name, &ko, &eng, &math);
		heapPush(name, ko, eng, math);
	}
	for (int i = 0; i < N; i++) {
		printf("%s\n", heapPop()->name);
	}
	return 0;
}

 

우선순위 큐는 우선 순위를 유지 하며 데이터를 추가 하고 삭제하는 자료구조이다.

요즘 B형에서는 HashTable + 우선순위 큐 모두 사용해야하는 경우가 많으므로 우선 순위 큐는 필수적이다.

하지만 우선순위 큐(Heap)는 구현량이 많다는 단점이 있어 미리 자료구조를 만들고 테스트 해봐서 실수를 안하는 것이 중요하다.