Tutorial: STL Sort 3 timer 1초 memory 256MB

지난 시간에 sort()를 이용하여 배열을 오름차순과 내림차순으로 정렬하는 방법을 배웠다.

오늘은 구조체를 이용하여 직접 만든 자료형으로 선언된 배열을 원하는 기준에 따라 정렬하는 방법을 배워보자. 

우선 설명에 들어가기 전에, 구조체로 선언된 배열을 정렬한다는게 무슨 말인지 생각해 보자.

예를 들어, 5명의 학생들의 이름과 점수를 입력 받아서, 점수가 낮은 순서부터 높은 순서대로 출력하는 프로그램을 작성한다고 생각해보자.

제일 간단한 방법은 역시 우리가 써오던 sort()함수를 사용하여 정렬하는 것이다.

아래 코드를 보자. (참고로 아래 코드는 컴파일되지 않는다.) 

- 컴파일되지 않는 코드 -

#include <cstdio> ///<stdio.h>와 동일
#include <algorithm>
using namespace std;
 
struct Student
{
    char name[ 20 ];
    int score;
};
 
int main()
{
    Student s[ 5 ];
    
    ///입력하고...
    for(int i = 0 ; i < 5 ; i++)
        scanf("%s %d" , s[i].name, &s[i].score);
    
    ///정렬하고...
    sort(s+0 , s+5);
    
    ///출력하고...
    for(int i = 0 ; i < 5 ; i++)
        printf("%s %d\n" , s[i].name, s[i].score);
    
    return 0;
}

위 코드를 컴파일하려고 하면, 에러와 경고가 엄청 많이 생기면서, 처음 보는 소스파일까지 자동으로 뜨는 기현상이 발생한다.

왜 이런 에러가 발생하게 될까?​

만약 s라는 이름의 배열이 int형 배열이라면, 위 코드는 전혀 문제가 되지 않는다.

왜냐? 두 int끼리는 대소비교가 가능하기 때문이다.

그러나 s라는 배열은 Student형 배열이다!

그리고 Student라는 자료형은 내가 방금 만든 자료형이기 때문에, 컴퓨터 입장에서는 당연히 대소비교를 하는 것이 불가능하여 정렬에 문제가 생기게 된다.

따라서, 에러의 해결 방법은 컴퓨터에게 두 Student형 자료를 비교하는 방법을 제시해주는 것이다.

이는 크게 두 가지 방법으로 나뉘게 된다. ​

방법 1. compare() 함수 작성

이전 강의에서 내림차순 정렬을 연습할 때 썼던 두 가지 방법 중 두 번째 방법과 같은 방법이다.

두 자료를 비교할 때, 왼쪽 값이 작으면 true를 리턴하게 하는 compare 함수를 작성했었던 기억이 나는가?

그 때는 두 int형 자료를 비교하는 코드를 작성했다.

이번엔 두 Student형 자료를 비교하게 하여, 앞의 자료가 작은 경우 true를 리턴하는 함수를 작성해 보자.

이후에 sort()함수 호출 시 이 함수의 이름을 3번째 인자로 보내주면, 컴퓨터는 이 함수를 통해 대소비교를 하게 된다.

#include <cstdio> ///<stdio.h>와 동일
#include <algorithm>
using namespace std;
 
struct Student
{
    char name[ 20 ];
    int score;
};
 
bool compare(const Student &l , const Student &r)
{
    return l.score <r.score;
}
int main()
{
    Student students[ 5 ];
 
    ///입력하고...
    for(int i = 0 ; i < 5 ; i++)
        scanf("%s %d" , students[i].name, &students[i].score);
 
    ///정렬하고...
    sort(students+0 , students+5 , compare);
 
    ///출력하고...
    for(int i = 0 ; i < 5 ; i++)
        printf("%s %d\n" , students[i].name, students[i].score);
 
    return 0;
}

참고) compare 함수 내에서 인자에 const와 참조형(&)을 붙이는 이유는 일단은 너무 신경 쓰지 말도록 하자.

(마치 우리가 scanf를 처음 학습할 때 변수명에 &를 붙이는 이유를 처음부터 배우지 않는 것과 마찬가지이다.

그래도 궁금한 사람들을 위해 문제 밑에 그 이유를 적어놓도록 하겠다. 원하는 학생들은 참고하도록 하자.)

방법 2. Student형을 정의할 때, 작다(<)연산자의 사용법 정의.

연산자 오버로딩을 이용하여 Student형 자료끼리 작다(<)연산을 사용 가능하게 만들어 놓으면, compare()같은 함수를 따로 작성하지 않더라도 sort()함수가 잘 작동하게 된다.

4641번문제(Tutorial: Operator Overloading)를 참고하여 연산자 오버로딩을 어느 정도 이해하고 왔을 거라고 믿는다. 연산자 오버로딩에 대한 이해가 완료된 후에 아래 코드를 보자.

#include <cstdio> ///<stdio.h>와 동일
#include <algorithm>
using namespace std;
 
struct Student
{
    char name[ 20 ];
    int score;
    bool operator<(const Student &r)const
    {
        return score<r.score;
    }
};
 
int main()
{
    Student students[ 5 ];
 
    ///입력하고...
    for(int i = 0 ; i < 5 ; i++)
        scanf("%s %d" , students[i].name, &students[i].score);
 
    ///정렬하고...
    sort(students+0 , students+5);
 
    ///출력하고...
    for(int i = 0 ; i < 5 ; i++)
        printf("%s %d\n" , students[i].name, students[i].score);
 
    return 0;
}  

두 Student형 자료끼리 작다(<)연산자를 사용 가능하게 만들어 놓았으므로, 정렬 기준이 명확하여 자료가 원하는 대로 정렬되게 된다.

참고) 방법 1과 마찬가지로 const와 참조형(&)를 사용하는 이유는 문제 밑에 적어놓을 테니, 궁금한 사람들은 참고하도록 하자. 지금 당장 이해하지 못하더라도 큰 상관은 없다.

응용문제를 풀어본 후에 다음으로 넘어갈 수 있도록 하자.

- 응용문제 -

n명의 학생의 이름과 수학 점수를 입력받아서,

수학 점수가 높은 순에서 낮은 순으로 정렬하여 출력하되, 수학 점수가 같은 학생끼리는 이름이 사전순으로 앞선 순서로 출력하는 프로그램을 작성하라.

반드시 sort()함수를 사용한다.