#include<algorithm> 그리고 sort()

🖥️ CS/Data Structure & Algorithm

#include<algorithm> 그리고 sort() - (2)

한국의 메타몽 2020. 3. 5. 02:50

링크 : https://www.youtube.com/watch?v=ZG68SXDtODM

공부 출처 링크 : 동빈나 유튜버

#inlcude<algorithm> - sort()와 연계했을때 알아두면 좋을 지식이 한 가지 더 있다. 바로 'pair'라는 기능이다.

utility 헤더 파일에 포함된 기능인데, utility 외에도 algorithm이나 vector에도 포함되어있다.

보통 정렬해야하는 값이 2개 이상일때 많이 사용된다.

기본적인 pair의 사용법은 아래와 같다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;


int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);  
    
    pair<int, char> p;
    p = make_pair(10, 'T');
    cout << p.first << " " << p.second << "\n";

    cout << "이번엔 직접 입력해보세요" << "\n";

    pair<int, char>p2;
    cin >> p2.first >> p2.second;
    cout << p2.first << " " << p2.second << "\n";

    return 0;
}

보통 정렬할 기준이 2개 이상인 경우, 프로그래밍 대회에서는 pair와 vector의 조합을 더 선호한다.

먼저 하단의 코드를 참고해보자.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main(void){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
  
    vector<pair<int, string>> v;
    v.push_back(pair<int, string>(90, "AA"));
    v.push_back(pair<int, string>(89, "BB"));
    v.push_back(pair<int, string>(92, "CC"));
    v.push_back(pair<int, string>(94, "DD"));
    
    sort(v.begin(), v.end());
    
    for(int i=0; i<v.size(); i++)
        cout << v[i].second << " : " << v[i].first << "\n";
    
    return 0;
}

기존의 배열 대신 vector를 사용했는데, 우선 당장은 둘의 차이가 크게 없다고 기억해두자.

pair는 말 그대로 '한 쌍'으로, 데이터들을 하나의 묶음으로 저장해둔다.

눈여겨봐야할 점은 출력에서 v[i].second를 먼저, 그리고 v[i].first를 그 다음으로 출력했는데,

직관적으로 pair에서 두 번째로 저장한 string형 변수, 즉, 문자열이 먼저 출력되고

그 다음으로 pair에서 첫 번째로 저장한 int형 변수, 즉, 숫자가 출력된다.

이러한 pair의 원리는 다음과 같은 상황에서 적용될 수 있다.

"학생의 이름, 생년원일, 성적이 제공 될 경우, 성적순으로 학생을 나열하고자 한다.

이때 동일점수가 나올 경우, 나이가 더 어린 학생이 우선 순위가 높다."

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

bool compare(pair<string, pair<int, int>>a,
             pair<string, pair<int, int>>b){
    if(a.second.first==b.second.first){
        return a.second.second > b.second.second;}
    else {
        return a.second.first>b.second.first;}
}

int main(void){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
  
    vector<pair<string, pair<int,int>>> v; // 이중 페어를 구현했다.
    v.push_back(pair<string, pair<int,int>>("Amma",pair<int,int>(99,960106)));
    v.push_back(pair<string, pair<int,int>>("Ollie",pair<int,int>(92,981106)));
    v.push_back(pair<string, pair<int,int>>("Chara",pair<int,int>(98,930166)));
    v.push_back(pair<string, pair<int,int>>("Magi",pair<int,int>(96,950108)));
    v.push_back(pair<string, pair<int,int>>("Asriel",pair<int,int>(99,970106)));

    sort(v.begin(),v.end(), compare);
    
    for(int i=0; i<5; i++)
        cout << v[i].first << " : " << v[i].second.first << "점 " << v[i].second.second << "년생" << "\n";
    
    return 0;
}

점수가 더 높을수록, 나이가 더 어릴수록 출력하는 결과가 나왔다.

눈여겨 봐야할 점은 'compare'함수이다.

a.second.first == b.second.first, 즉, 둘의 점수가 같을 경우

a.second.second > b.second.second가 TRUE일 경우, 다시 말해 '태어난 연도의 숫자가 클수록', '나이가 더 어릴수록'

먼저 출력함을 의미한다. 만 나이가 아닌 생년월일을 기준으로 했으므로, 숫자가 크면 나이가 더 어리다는 것을 간과해서는 안된다.

else 문장에서는 만약 점수가 겹치지 않을 경우, 단순하게 점수가 더 큰쪽을 먼저 출력하도록 설정했다.

first와 second가 무엇을 의미하는지는 알겠어요!

그런데 나중에 코드를 다시 확인할 때 헷갈릴 수 있겠네요.

함수의 이름을 정의해서 사용하고 싶어요!

이 경우엔 '오버로딩'을 사용하면 된다.

내 경우에는 이 방법이 더 코드의 함수명을 이해하는데 직관적이라고 느껴진다.

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

using namespace std;

class Person{
public:
    string name;
    int age;
    Person(string name, int age){
        this->name = name;
        this->age = age;
    }
    bool operator <(const Person &a) const {
        return this->age < a.age;
    }

};

int main(){
    vector<Person> v;
    v.push_back(Person("MinJi", 22));
    v.push_back(Person("Kangho", 28));
    v.push_back(Person("Minho", 26));
    v.push_back(Person("Strange Yun", 25));
    v.push_back(Person("JunEun", 40));
    sort(v.begin(), v.end());
    for (int i = 0; i < v.size(); i++)
        cout << v[i].age  << ", " <<  v[i].name << endl;

}

↓결과

22, MinJi
25, Strange Yun
26, Minho
28, Kangho
40, JunEun