[백준] 10814번 : 나이순 정렬 - C/C++

 

 

 

내가 생각한 문제 해결 순서는 아래와 같다.

 

1. 회원수 n 입력하기

2. 회원의 나이와 이름 입력하기

3. 나이순으로 출력하기

 

문제는 간단했는데
이걸 2차원배열로 입력으로 받아버리면.. 시간 초과가 뜰 것 같았다.

 

그래서 방법을 생각하다가

얼마전 알고리즘 강의에서 배운 pair 를 사용해보기로 했다.

 

pair 선언은 아래처럼 할 수 있다.

vector<pair<int,string>> vector;

 

-pair??

pair<[Type],[Type]> 가 기본 구조이다.

특징은 아래와 같다.

 

• 저장한 값은 .first 그리고 .second로 접근할 수 있다.
• 2개의 값을 순서쌍 형태로 저장할 수 있다.
• 정렬에 용이하게 사용된다.

 

우리는 입력 받은 n 만큼의 쌍을 입력 받아야하니까

for 문을 돌려준다.

for (int i = 0; i < n; i++) {
    int num;
    string str;
    cin >> num >> str;
    vector.emplace_back(num, i, str);
}

 

vector에 입력하고 추가하는 것은 아래처럼도 할 수 있다.

vector.emplace_back(num, str);

하지만 i를 추가한 이유는 문제의 조건 때문이었다.

"만약 나이가 같다면, 입력한 순서대로 출력하기."

 

그리고 나이 순으로 정렬하기

sort(vector.begin(), vector.end());

sort가 계속해서 반복된다.

익숙해지자.

 

그리고 이제 정렬된 데이터를 출력해보자.

for (const auto& p : vector) {
    cout << p.first << " " << p.second << "\n";
}

 

vscode에서는 정상 작동했다.

그래서 제출했더니,,

컴파일 에러??

 

어떻게하면 컴파일 에러가 뜰까..

 

런타임 에러도 아니고...

고민을 했다.

 

python에는 값을 수정할 수 없는 tuple이라는 개념이 존재한다.

순서를 매기는 것이다.

이걸 c++에 적용해보자.

 

vector 부터 다시 선언하자.

vector<tuple<int,string>> vector;

pair 대신 tuple 사용하기

 

다음으로, sort는 기본 quick sort(퀵 정렬)이 아닌 다른 개념을 사용해야한다.

안정 정렬(Stable Sort, Merge Sort 기반) 을 사용하자.

 

안정 정렬을 기존 순서(예제 문제로 치면 '가입 순서')를 유지하는 정렬이라고 한다.

stable_sort를 사용하지 않고 문제에서 주어진 예제 입력을 입력하면,

이렇게 Dohyun과 Junkyu의 순서가 바뀌어서 출력된다.

이런 상황을 막기 위해서 stable_sort를 사용하는 것이다.

 

코드로는 아래와 같이 작성 가능하다.

stable_sort(vector.begin(), vector.end(), [](const auto& a, const auto& b) {
     return get<0>(a) < get<0>(b);  //나이순 정렬. 오름차순
});

 

이렇게 작성하면 나이순으로 우선 정렬되고,

나이가 같다면 가입 순서대로 정렬이 된다.

 

 

 

 

전체 코드

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

//나이순 정렬
using namespace std;

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

    //vector<pair<int,string>> vector;
    vector<tuple<int,string>> vector;

    for (int i = 0; i < n; i++) {
        int num;
        string str;
        cin >> num >> str;
        vector.emplace_back(num,str); //벡터에 값 추가
    }
    //sort(vector.begin(), vector.end());

    /*
    for (const auto& p : vector) {
        cout << p.first << " " << p.second << "\n";
    }
    */
    stable_sort(vector.begin(), vector.end(), [](const auto& a, const auto& b) {
        return get<0>(a) < get<0>(b);  //나이순 정렬. 오름차순
    });

    for (const auto& [num,str] : vector) {
        cout << num << " " << str << "\n";
    }
    return 0;
}

 

 

필자가 처음에 pair로 풀었던 코드는 주석처리 해 두었다.

혹시,, 필자와 같은 실수를 한 사람이 있을 수도 있으니

 

 

 

실버5의 난이도였다.

실버 난이도로 올라가니 한번에 생각할 수 있는 풀이가 아닌 것 같았다.

안정 정렬이라는 것은 이번에 처음 접하는 것 같다.

어딘가에서 들어봤는데 내가 까먹은 걸 수도..

이번 문제를 솔브 하면서 새로운 개념을 얻어갈 수 있었던 것 같다.

 

 

 

 

 

 

 

더 좋은 풀이가 있다면 댓글로 알려주세요 !!

피드백 환영입니다☺️