sort 정렬 순서 커스텀하기 (feat. 백준 8979)

C++ algorithm 헤더에 포함된 sort()함수를 사용하면 쉽게 배열이나 벡터 등을 정렬할 수 있다.

 

Sort() 사용법

sort(배열 시작점 주소, 배열의 마지막주소 + 1)

#include <iostream>
#include <algorithm>

int main() {

	int arr[10] = { 2, 3, 6, 5, 1, 4, 7, 9, 8, 10 };

	sort(arr, arr + 10); // arr 배열 오름차순 정렬

	return 0;
}

기본적으로 sort()는 오름차순으로 정렬이 진행되는데 만약 내림차순으로 정렬해주고 싶으면 sort()의 세번째 매개변수로 cmp함수를 만들어 넘겨주면 내림차순으로 정렬이 가능하다.

#include <iostream>
#include <algorithm>

bool cmp(int a, int b) {
	return a > b;
}

int main() {

	int arr[10] = { 2, 3, 6, 5, 1, 4, 7, 9, 8, 10 };

	sort(arr, arr + 10, cmp);

	return 0;
}

원하는 순서로 구조체 정렬하기

sort()의 정렬 기준을 정하는 cmp()의 규칙은 다음과 같다.

1. 내가 원하는 순서일경우 0이아닌값 리턴

2. 내가 원하지 않는 순서일경우 0 리턴

 

위의 내림차순 정렬 cmp함수를 살펴보면 왼쪽에 있는수 a 가 오른쪽에 있는수 b보다 클경우 1을 반환 (올바른순서) 즉, 큰수가 왼쪽에 있는 내림차순 정렬이 된다.

 

이러한 원리를 이용하여 구조체의 값에 따라 커스텀하여 정렬을 수행할수 있다.

 

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

8979번: 올림픽

위 문제는 각 나라별로 금메달, 은메달, 동매달 획득 갯수를 입력으로 주어지고 다음과 같은 순서로 등수를 매긴다.

1. 금메달이 많은나라가 순위가 더 높다.

2. 금메달의 수가 같다면 은메달이 많은 나라의 순위가 높다

3. 은메달의 수가 같다면 동메달이 많은 나라의 순위가 높다.

 

따라서 각 나라의 메달수를 담는 구조체를 선언해두고 위의 조건을 만족하도록 오름차순 정렬을하면 각 나라면 순위를 구할수 있게된다. 

typedef struct country {
	int index;
	int gold;
	int silver;
	int bronze;
}country;

country score[1000];

bool cmp(const country &a, const country &b) {
	if (a.gold > b.gold)
		return true;
	else if (a.gold == b.gold) {
		if (a.silver > b.silver)
			return true;
		else if (a.silver == b.silver) {
			if (a.bronze > b.bronze) {
				return true;
			}
		}
	}
	
	return false;
}


int main() {

	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int n, k, index;

	cin >> n >> k;
	
	for (int i = 0; i < n; i++) { // 배열 값들을 입력받음
		cin >> score[i].index >> score[i].gold >> score[i].silver >> score[i].bronze;
	}

	sort(score, score + n, cmp); // 정렬수행
	

	return 0;
}

 

cmp함수를 살펴보면 문제에서 제시한 조건에 맞게 코드를 작성한것을 확인할 수 있다.

1. 왼쪽에 있는 나라의 금메달수가 오른쪽에 있는 나라보다 많다면 true(올바른순서임을 명시)

2. 왼쪽과 오른쪽 나라의 금메달 수가 같다면 왼쪽나라의 은메달 수가 더 많은경우 true

3. 왼쪽 오른족 나라의 은메달 수도 같다면 왼쪽 나라의 동메달 수가 더 많은 경우 true

4. 그렇지 않은 경우 false(올바르지 않은 순서)