[BaekJoon 10814][⚪5] 나이순 정렬

❓ 문제

백준 10814 - “나이순 정렬”

🎯 난이도

Silver ⚪5

🧠 풀이

1. 내 풀이 (정렬 + tuple)

- 알고리즘

• Sorting

- 설명

tuple과 sort를 사용해 정렬하는 방식이다.

사실 이런 문제처럼 여러 데이터를 저장해야 하는 경우에는 구조체를 만들어서 하는게 가시성도 좋고 깔끔하다. 하지만 이런 기회에 tuple을 써서 풀어보고 싶었다.

나머지는 그냥 sort를 사용해 푸는 평범한 풀이이다.

전체 시간 복잡도는 sort의 시간 복잡도이므로 O(N log N)이다.

- 코드

내 풀이 코드

#include <iostream>

#include <vector>

#include <string>

#include <tuple>

#include <algorithm>


using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int iN{};
    cin >> iN;

    vector<tuple<int, int, string>> vecUser(iN);

    for(int i = 0; i < iN; ++i)
    {
        int iAge{};
        string strName{};
        cin >> iAge >> strName;

        tuple<int, int, string> tpUser{iAge, i, strName};
        vecUser[i] = tpUser;
    }

    // 나이순 + 원래 순서 기반으로 정렬
    sort(vecUser.begin(), vecUser.end(), [](const auto& tpPrev, const auto& tpNext)
    {
        if(get<0>(tpPrev) == get<0>(tpNext))
        {
            return get<1>(tpPrev) < get<1>(tpNext);
        }

        return get<0>(tpPrev) < get<0>(tpNext);
    });

    for(const auto& tpUser : vecUser)
    {
        cout << get<0>(tpUser) << ' ' << get<2>(tpUser) << '\n';
    }

    return 0;
}

---

2. 추가 풀이 1 (stable_sort 정렬)

- 알고리즘

• Sorting

- 설명

stable_sort를 사용해 정렬하는 방식이다.

sort가 아닌 stable_sort를 사용하는 풀이이다. stable_sort는 sort와는 다르게 대부분이 병합 정렬 방식으로 작동하며, 원래의 상대적인 순서를 유지하면서 정렬한다. 따라서 이런 문제처럼 입력 받은 순서를 보장하며 나이순으로만 정렬하는데 딱 맞는 STL 함수라고 볼 수 있다.

stable_sort는 병합 정렬로, 시간 복잡도는 O(N log N)이다.

- 코드

내 풀이 코드

#include <iostream>

#include <vector>

#include <string>

#include <algorithm>


using namespace std;

// 사용자 정보를 struct로 묶어줌
struct User
{
    int iAge{};
    string strName{};
};

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int iN{};
    cin >> iN;

    vector<User> vecUser(iN);

    for(int i = 0; i < iN; ++i)
    {
        User tUser{};
        cin >> tUser.iAge >> tUser.strName;

        vecUser[i] = tUser;
    }

    // stable_sort를 사용해서 원래 상대적인 순서를 바꾸지 않으면서 정렬
    stable_sort(vecUser.begin(), vecUser.end(), [](const auto& tPrev, const auto& tNext)
    {
        return tPrev.iAge < tNext.iAge;
    });

    for(const auto& tUser : vecUser)
    {
        cout << tUser.iAge << ' ' << tUser.strName << '\n';
    }

    return 0;
}

---

3. 추가 풀이 2 (미정렬 풀이)

- 알고리즘

• Sorting

- 설명

정렬을 하지 않는 풀이이다.

정렬을 하지 않는 대신, 나이가 1 <= N <= 200이라는 조건을 기반으로 이중 vector를 만들고 나이를 인덱스로 사용해 알맞는 인덱스의 vector에 이름을 삽입하는 방식이다.

이렇게 하면 정렬의 알고리즘을 사용하지 않으면서도, 입력된 순서 그대로 이름이 정렬되므로 가장 최적화된 방식이라고 볼 수 있다.

정렬을 하지 않고 입력 받은 값을 그대로 출력하는 것 뿐이므로, 시간 복잡도는 O(N)이다.

- 코드

내 풀이 코드

#include <iostream>

#include <vector>

#include <string>


using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int iN{};
    cin >> iN;

    // 미리 나이 범위의 vector 생성
    vector<vector<string>> vecUser(201);

    for(int i = 0; i < iN; ++i)
    {
        int iAge{};
        string strName{};
        cin >> iAge >> strName;

        // 해당 나이의 인덱스에 있는 vector에 이름 push_back
        vecUser[iAge].push_back(strName);
    }

    // 나이순 + 각 벡터의 인덱스 순으로 출력
    for(int i = 1; i <= 200; ++i)
    {
        for(const string& strName : vecUser[i])
        {
            cout << i << ' ' << strName << '\n';
        }
    }

    return 0;
}

---

💭 후기

가장 최적화된 풀이는 세 번째 풀이로, 시간 복잡도로 봐도 그렇지만 실제로 걸리는 시간도 가장 적다.

• 첫 번째 풀이 : 36ms
• 두 번째 풀이 : 36ms
• 세 번째 풀이 : 24ms

그래도 가장 의도가 보이면서 가독성이 좋은건 두 번째 풀이라고 볼 수 있다. stable_sort를 사용함으로써 원래 상대 순서를 보존하겠다는 의도가 보이기 때문이다.

하지만 주의할 점은 stable_sort는 병합 정렬 방식으로, sort보다 상수 시간이 좀 더 생길 수 있다는 것이다.