BOJ 10825 : 국영수

삼성 B형 전체 링크
 
www.acmicpc.net/problem/10825
 

 
정렬의 방법은 다양하지만 우선순위 큐 응용을 위해 힙으로 풀어보자.
 
우선순위가 높은 순은 다음과 같다.
1) 국어 점수가 높다.
2) 국어 점수가 같으면 영어 점수는 낮은 순.
3) 영어 점수까지 같으면 수학 점수가 높은 순.
4) 모두 같은 점수면 이름의 사전 순.
 
따라서 pop을 할 때, 최악의 input은 아래와 같다.

heap[hn].kr = 0;                         /* 낮은 국어 점수 */
heap[hn].en = 0x7fff0000;                /* 높은 영어 점수 */
heap[hn--].math = 0;                     /* 낮은 수학 점수 */
mystrcpy(heap[hn--].name, "zzzzzzzzzz"); /* 사전 순으로 가장 뒤의 이름 */

 
우선순위 조건으로 비교 함수는 HEAP을 통째로 비교한다.

int isMin(HEAP a, HEAP b)
{
	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 isMin(HEAP a, HEAP b) 
{
    if (a.kr != b.kr) return a.kr > b.kr;
    if (a.en != b.en) return a.en < b.en;
    if (a.math != b.math) return a.math > b.math;

    return mystrcmp(a.name, b.name) < 0;
}

최종 코드는 아래를 참고하자.

#include <stdio.h>

int N;

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

HEAP heap[100100];
int hn;

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)
{
	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 pop(HEAP* heap, int& hn)
{
	register HEAP ret, tmp;

	ret = heap[1];
	heap[1] = heap[hn];
	heap[hn].kr = 0;
	heap[hn].en = 0x7fff0000;
	heap[hn].math = 0;
	mystrcpy(heap[hn--].name, "zzzzzzzzzz");

	for (register int i = 1; i * 2 <= hn;)
	{
		if (isMin(heap[i], heap[i * 2]) && isMin(heap[i], heap[i * 2 + 1])) break;
		else if (isMin(heap[i * 2], heap[i * 2 + 1]))
		{
			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 push(HEAP* heap, int& hn, HEAP x)
{
	register HEAP tmp;

	heap[++hn] = x;

	for (register int i = hn; i > 1; i /= 2)
	{
		if (isMin(heap[i / 2], heap[i])) return;

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

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

		push(heap, hn, x);
	}

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

	return 0;
}