BOJ 10825 : 국영수 (priority_queue, compare)

삼성 B형 전체 링크

 

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

 

 

이번에는 BOJ 10825 : 국영수 문제를 STL로 풀어보자.

즉, 구조체에 대한 우선순위를 compare에 적용시켜보자.

---

먼저 HEAP의 char name[15]; 는 string으로 변경하였다.

typedef struct st
{
	string name; // char name[15];
	int kr;
	int en;
	int math;
}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;
}

 

따라서 compare는 아래와 같이 변경된다.

struct compare
{
	bool operator()(const HEAP& parent, const HEAP& child) const
	{
		if (parent.kr < child.kr) return true;
		if (parent.kr == child.kr)
		{
			if (parent.en > child.en) return true;

			if (parent.en == child.en)
			{
				if (parent.math < child.math) return true;

				if (parent.math == child.math)
				{
					if (parent.name > child.name) return true;
				}
			}
		}

		return false;
	}
};

 

그리고 구조체에 대한 priority queue이므로 pq의 type과 vector의 type이 구조체로 변경된다.

priority_queue<HEAP, vector<HEAP>, compare> pq;

void pq_clear(priority_queue<HEAP, vector<HEAP>, compare>& pq)
{
	priority_queue<HEAP, vector<HEAP>, compare> reset;
	swap(pq, reset);
}

타입 변경에 따라 clear도 변경된다.

 

최종 코드는 아래와 같다.

#include <stdio.h>
#include <iostream>
#include <string>
#include <queue>

using namespace std;

int N;

typedef struct st
{
	string name;
	int kr;
	int en;
	int math;
}HEAP;

struct compare
{
	bool operator()(const HEAP& parent, const HEAP& child) const
	{
		if (parent.kr < child.kr) return true;
		if (parent.kr == child.kr)
		{
			if (parent.en > child.en) return true;

			if (parent.en == child.en)
			{
				if (parent.math < child.math) return true;

				if (parent.math == child.math)
				{
					if (parent.name > child.name) return true;
				}
			}
		}

		return false;
	}
};

priority_queue<HEAP, vector<HEAP>, compare> pq;

void pq_clear(priority_queue<HEAP, vector<HEAP>, compare>& pq)
{
	priority_queue<HEAP, vector<HEAP>, compare> reset;
	swap(pq, reset);
}

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

	pq_clear(pq);

	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;
		x.name = string(str);

		pq.push(x);
	}

	for (int i = 0; i < N; i++)
	{
		HEAP tmp = pq.top();

		pq.pop();

		printf("%s\n", tmp.name.c_str());
	}

	return 0;
}