JUNGOL...116

Intermediate_Coder/분할정복/Tutorial: STL Sort 3

---

문제                                            

지난 시간에 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()함수를 사용한다.

 

입력 형식                                     

첫 줄에 학생의 수 n(1≤n≤50,000)이 주어진다.

 

다음 n줄에 걸쳐 이름(20자 이내의 소문자로만 이루어진 문자열)과 수학 점수(0이상 100이하의 정수)가 공백을 사이에 두고 주어진다.

이름과 수학 점수가 같은 학생이 입력자료로 주어질 수도 있다. 

 

출력 형식                                     

주어진 조건대로 학생들의 정보를 정렬한 후, n줄에 걸쳐 각 학생의 이름과 수학 점수를 공백을 사이에 두고 출력한다.

 

입력 예                                        

5
jinho 100
junho 90
minho 80
minho 90
dongho 90

 

출력 예                                        

jinho 100
dongho 90
junho 90
minho 90
minho 80

 

Hint!

힌트

방법 1을 사용하든 방법 2를 사용하든, 대소비교 함수를 작성할 때 다음과 같은 방법을 사용한다.

① 수학 점수가 서로 다른지 확인한다.

② 서로 다르면, 두 자료 중에서 왼쪽 자료의 수학 점수가 높을 때 true를 리턴하게 한다.

③ 서로 같으면, 두 자료 중에서 왼쪽 자료의 이름이 사전순으로 낮을 때 true를 리턴하게 한다. 이 때 strcmp()를 써야 함을 잊지 말도록 하자.

 

이 아래는 코드를 공부할 때 완벽히 이해하지 않고 넘어가면 병에 걸리는 사람들(혹은 완벽주의자들)만 읽도록 하자.

 

- const 에 관하여 -

 

const로 선언된 변수나 매개변수는, 한 번 값이 정해지면, 두 번 다시 그 값을 변경하지 못한다.

이런 변수를 변수라고 부르지 않고, 상수(constant)라고 한다. 

누군가가 상수의 값을 변경하려는 시도를 하면, 컴파일 단계에서 에러를 표시해준다. 즉, 일종의 "안전장치"역할을 하는 것이라고 볼 수 있다.

 

방법 1이든 방법 2든 상관없이, 대소비교 함수에서 받은 매개변수를 변경해서는 안되기 때문에, const를 붙여준다.

예를 들어 방법 1에서 아래 문장을 보면,

bool compare(const Student &l , const Student &r)

l과 r은 compare 함수 내에서 값의 변경이 있을 이유가 없으므로(compare의 목적이 비교임을 잊지 말도록 하자), const를 추가해주는 것이 정당하다.

 

방법 2의 경우

bool operator<(const Student &r)const

라는 문장이 있다. 해당 문장을 보면 맨 뒤에 const가 하나 더 써있는데, 이것은 상수 선언이 아니라, 함수 내에서 대입 연산이 이루어지지 못하게 하는 장치이다. 

대소비교 함수이기 때문에 const를 붙여주는 것이 정당하다. 이 함수 내에서 대입 연산이 이루어질 필요가 전혀 없기 때문이다.

 

여기까지 읽고 들을 수 있는 의문점이 있다. 

앞에서 살펴본 두 가지 종류의 const는 모두 일종의 안전장치이다.

헌데 왜 이 튜토리얼에서는 선택사항이 아니고, 반드시 적으라고 식으로 유도하는 것일까?

 

STL(Standard Template Library, sort()처럼 미리 작성된 다양한 기능의 집합을 말한다) 기능의 대부분은 const 안전장치가 되어있지 않은 경우 사용할 수 없도록 만들어 놨기 때문이다.

즉, 좋은 코딩 습관을 위해서뿐만이 아니라, 나중에 여러분들이 STL의 다른 기능을 쓸 때도 문제가 없도록 미리 선수를 치는것이다.

참고로 sort()의 경우, 사실 const를 쓰지 않더라도 아무 문제가 없이 잘 작동한다.

그러나, 우리가 이후에 배울 STL의 다른 기능을 쓸 때는 에러가 발생하게 되기 때문에, 미리 에러나지 않게 코드를 쓰는 연습을 하는 것이다.

 

- 참조형(&)에 관하여 -

 

다음 두 가지 함수를 고려해 보자.

 

bool compare(const Student l , const Student r)   /// ① "값에 의한" 전달. (call by value)

bool compare(const Student & l , const Student & r) /// ② "참조에 의한" 전달 (call by reference)

 

①의 경우 다음과 같이 작동한다.

-      메모리 상에 l과 r이라는 변수(또는 상수)를 저장할 공간을 새로 만든다.

-      l과 r에 인자로 전달받은 값을 복사한다.

②의 경우 다음과 같이 작동한다.

-      메모리 상에 새로운 공간을 따로 잡지 않는다.

-      l과 r은 단순히 전달받은 인자와 같은 공간을 가리키는 또 다른 별칭(alias)가 된다.

①의 경우 메모리를 잡고, 값을 복사하는 과정이 생기기 때문에 참조형으로 호출하는 ②의 경우보다 조금 비효율적이다. 그래서 매개변수를 참조형으로 전달하는 것이다.

 

const와 마찬가지로, sort()함수만 사용할 때는 참조형으로 작성하지 않아도 크게 문제가 없지만, STL의 다른 기능을 사용할 때 참조형으로 적지 않으면 에러가 발생하게 된다. 

---

STLSort3.h

#include <iostream>
#include <algorithm>
#include <string>

using std::string;

class STLSort3 : public Base
{
private:
	struct Student
	{
		string name;
		int score;

		bool operator <(const Student& other);
		friend std::istream& operator >>(std::istream& is, Student& student)
		{
			is >> student.name >> student.score;
			return is;
		}
		friend std::ostream& operator <<(std::ostream& os, const Student& student)
		{
			os << student.name << ' ' << student.score;
			return os;
		}
	};

	void SortDesc(Student arr[], int n);
};

 

STLSort3.cpp

void STLSort3::Code()
{
	int n;
	std::cin >> n;

	Student* arr = new Student[n];
	for (int i = 0; i < n; i++)
	{
		std::cin >> arr[i];
	}

	SortDesc(arr, n);

	for (int i = 0; i < n; i++)
	{
		std::cout << arr[i] << '\n';
	}

	delete[] arr;
}

/// <summary>
/// 비교 연산 오버로딩, 점수 비교 후 점수 동일하면 이름으로 비교
/// </summary>
/// <param name="other">비교할 다른 학생</param>
/// <returns>기준 값이 작은지 여부</returns>
bool STLSort3::Student::operator <(const Student& other)
{
	if (score == other.score)
	{
		return name > other.name;
	}
	return score < other.score;
}

/// <summary>
/// 주어진 배열을 내림차순으로 정렬한다.
/// </summary>
/// <param name="arr">배열</param>
/// <param name="n">배열의 길이</param>
void STLSort3::SortDesc(Student arr[], int n)
{
	std::sort(arr, arr + n);
	std::reverse(arr, arr + n);
}

 

---

실행 결과 Success(100)

---

 

NadanKim/CodingTest_JUNGOL: JUNGOL 코딩 테스트를 위한 저장소 (github.com)

NadanKim/CodingTest_JUNGOL

 

문제출처

Intermediate_Coder/분할정복/Tutorial: STL Sort 3-JUNGOL