[STL 알고리즘] sort - 구조체 정렬

▶ [STL 알고리즘] sort - 구조체 정렬

알고리즘 문제를 해결하다보면 구조체를 정렬해야 할 경우가 생긴다.

STL 알고리즘 중에 컨테이너를 정렬해주는 sort가 있다. 이를 활용하여 구조체를 정렬하는 방법을 알아보자.

이해하기 쉽도록 간단한 문제를 만들어서 sort를 사용해 문제를 해결하는 과정을 설명하려한다.

▶ 문제

---

우리는 사람 10명의 이름, 나이, 키, 몸무게를 알고있다.

10명의 사람들 중 모델이 될 사람을 뽑아야 한다.

그래서 키가 가장 크고, 몸무게가 적게 나가면서, 어린 사람을 찾으려 한다.

키가 큰 사람을 우선하는데, 키가 같은 경우에는 몸무게가 적은 사람을 우선하고,

키가 같으면서 몸무게도 같은 경우에는 어린 사람을 우선한다.

STL 알고리즘 중 sort를 활용해서 문제를 해결하라.

▶ 설계

---

우선 Person 구조체를 만들어보자.

struct Person{
    string name;
    int age, height, weight;
}persons[10];

이런 구조체를 만들면 사람 한명에 대한 정보를 묶어서 관리할 수 있게 된다.

sort()를 이용해 정렬하기위해 어떤 비교 함수를 구현해야 할까?

bool compare(const Person& p1, const Person& p2){
    if(p1.height == p2.height){
        if(p1.weight == p2.weight){
            return p1.age < p2.age;    
        }
        else
            return p1.weight < p2.weight;
    }
    else
        return p1.height > p2.height;
}

부등호의 방향이 헛갈린다면 병합 정렬 알고리즘을 생각해보자.

왼쪽과 오른쪽으로 각각 정렬된 배열이 있을 때, 

앞에서부터 왼쪽 배열의 값은 L로, 오른쪽 배열의 값은 R로 가리킨다고 하자.

두 배열을 합치면서 비교하게 되는데

L과 R을 비교 함수의 인자로 순서대로 넣어 호출했을 때 ( compare(L,R) )

true를 반환하면 L, false를 반환하면 R이 합쳐진 배열의 가장 앞에 오도록 구현되어있다고 생각하면 된다.

즉, 비교함수로 compare함수를 인자로 넘겨주면 배열의 0번 인덱스에 원하는 사람이 있게 된다.

▶ 구현

---

코드 상단에 #include<algorithm>을  추가해주었다.

algorithm에 sort함수가 정의되어 있기 때문이다.

작성된 메인문을 보자.

int main(){
    freopen("input.txt","r",stdin);
    for(int i=0; i<NUM_PERSONS ;i++){
        Person& p = persons[i];
        cin >> p.name >> p.age >> p.height >> p.weight;
    }
    printArray(persons, NUM_PERSONS);
    sort(persons, persons+NUM_PERSONS, compare);
    printArray(persons, NUM_PERSONS);
 
    cout<< "answer :" << persons[0].name << endl;
    return 0;
}

정렬이 이루어지는 부분은 8번째 라인 한 줄 뿐이다.

첫 번째 인자 : 정렬을 수행할 배열의 이름 ( 배열의 시작주소, vector의 begin() ) 

두 번째 인자 : 정렬을 수행할 배열의 마지막 인덱스의 주소값 + 1 ( 배열의 끝주소, vecctor의 end() )

얼마나 편리한가?

이처럼 STL 함수 사용 방법을 익혀두는 것은 매우 중요하다.

▶ 결과

---

▶Solution

---

[소스코드 보기]