[백준] 10814 나이순 정렬 - 정렬

[ 문제링크 ]

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

 

🚩 조건

1. 첫째 줄에 온라인 저지 회원의 수 N이 주어짐 (1 ≤ N ≤ 100,000)
2. 각 N개의 줄에 회원의 나이와 이름이 공백으로 구분되어 주어짐
3. 회원을 나이 순, 나이가 같으면 가입한 순으로 정렬하여 나이와 이름을 출력해라

 

 

🚩 접근

3 -> vector<pair<나이, 이름>>을 만들어서  sort 함수 사용하자

 

 

🚩 시행착오

vector<pair<나이, 이름>>을 sort 함수를 통해 정렬하면 가입순으로 정렬될거란 보장이 없다. 따라서 <나이, 가입순서, 이름>을 저장하고자 하였고, 원소가 3개이므로 tuple을 사용해야 한다.

#include <tuple>

vector<tuple<int, int, string>> v;

// 새로운 tuple을 만드는 것은 pair와 유사함
v.push_back(make_tuple(age, i, name));

// tuple 원소에 접근하는 방법
get<0>(v[i]);	// ex) 21
get<1>(v[i]);	// ex) 2
get<2>(v[i]);	// ex) Yewon

 

그리고 sort 함수에 사용할 새로운 연산자를 정의해줘야 한다. 만약 첫번째 원소의 값이 같으면 두번째 원소의 크기순이 곧 순서가 되고, 그게 아니라면 첫번째 원소의 크기순(오름차순)이 곧 순서가 된다. 그리고 인자에 레퍼런스(&)를 붙여주는 것이 런타임 에러 발생 확률을 줄인다.(값 복사하지 않고 바로 참조)

// 인자의 타입이 vector<tuple<int, int, string>>가 아니라
// tuple<int, int, string>임에 유의
bool cmp(const tuple<int, int, string> &t1, const tuple<int, int, string> &t2){
    if(get<0>(t1)==get<0>(t2))
        return get<1>(t1) < get<1>(t2);
    return get<0>(t1) < get<0>(t2);
}

 

 

💻 코드 (C++)

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

vector<tuple<int, int, string>> v;

bool cmp(const tuple<int, int, string> t1, const tuple<int, int, string> t2){
    if(get<0>(t1)==get<0>(t2))
        return get<1>(t1) < get<1>(t2);
    return get<0>(t1) < get<0>(t2);
}

int main(){
    int N;
    cin >> N;
    
    for(int i=0; i<N; i++){
        int age; string name;
        cin >> age >> name;
        v.push_back(make_tuple(age, i, name));
    }
    sort(v.begin(), v.end(), cmp);
    
    for(int i=0; i<N; i++){
        cout << get<0>(v[i]) << " " << get<2>(v[i]) << "\n";
    }
}

 

+ stable_sort

<algorithm> 헤더파일의 stable_sort 함수를 사용하면 더 간단하게 코드를 작성할 수 있다.

stable_sort는 우선순위가 같은 원소들끼리는 원래의 순서를 따라가도록 하는 정렬이다. 이 때 비교함수를 반드시 정의해야 stable_sort가 잘 동작한다.

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

vector<pair<int, string>> v;

bool cmp(const pair<int, string> p1, const pair<int, string> p2) {
    return p1.first < p2.first;
}

int main() {
    int N;
    cin >> N;

    for (int i = 0; i < N; i++) {
        int age; string name;
        cin >> age >> name;
        v.push_back(make_pair(age, name));
    }
    stable_sort(v.begin(), v.end(), cmp);

    for (int i = 0; i < N; i++) {
        cout << v[i].first << " " << v[i].second << "\n";
    }
}