[C++] 백준 10814 나이순 정렬

www.acmicpc.net/problem/10814

10814번: 나이순 정렬

 

1. 서론

 

어렵게 풀면 어렵고, 쉽게 풀면 쉬운 문제....

 

2. 문제 풀이

 

온라인 사이트의 회원 나이와 이름이 주어진다. 주어지는 순서는 가입한 순서이며 나이가 어린 순서대로 정렬하는데 만약 나이가 같으면 가입한 순서대로 정렬한다.

 

문제는 엄청 간단한데 그럴수록 생각이 많아진다. 나는 가입한 순서대로 정렬하는 거에 너무 집중해서 너무 어렵게 생각했는데 별거 아니었다. 

 

처음에는 가입한 순서에 집중해 나이, 이름, 가입한 순서 세 가지가 다 필요할 것 같아서 구조체를 만들어서 풀었다. 나이 때로 정렬하되, 만약 나이가 같은 경우에는 가입한 순서를 보는 식이다. 이렇게 푼 이유는 compare를 따로 만들더라도 가입한 순서대로 정렬하는 게 어려울 것 같아서였는데 결과적으로 말하자면 구조체를 만들지 않고 compare만으로도 가입한 순서대로 정렬하는 게 가능했다.

 

그래서 코드를 다시 짰는데 compare에서 그냥 나이에 따라 정렬하게하고 그냥 sort 함수 대신에 stable_sort를 사용하면 그게 가능하다. 근데 이런 함수가 있다는 걸 이 문제를 풀며 처음 알았다^^... C++ 문법을 그냥 문제 풀면서 필요한 것만 찾아봐서 그런지,, 모르는 게 투성이다.

 

xone.tistory.com/3

[STL] sort와 stable_sort 에 대해 알아보자

이 블로그에 sort, stable_sort 그리고 이 문제에 대해 자세히 나와있다.

그냥 sort는 퀵소트, stable_sort는 머지 소트를 사용하는데

퀵 소트는 재귀로, 머지 소트는 반씩 쪼개서 순서대로 정렬하기 때문에 이런 차이가 발생하는 것 같다.

 

즉, 퀵소트는 값을 무작위로 쪼개서 정렬하고, 머지 소트는 순서대로 쪼개서 정렬하기 때문에 compare에서 따로 정해줄 필요 없이 알아서 순서대로 정렬해주는 것이다.

 

3. 코드 설명

 

1) 첫 번째 방법

 

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

using namespace std;

struct AgeSort
{
    int i, age;
    string name;
};

bool compare(AgeSort a, AgeSort b)
{
    if (a.age == b.age)
        return a.i < b.i;
    else
        return a.age < b.age;
}

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

    AgeSort a[n];
    for (i = 0; i < n; i++)
    {
        a[i].i = i;
        cin >> a[i].age >> a[i].name;
    }

    sort(a, a + n, compare);

    for (i = 0; i < n; i++)
        printf("%d %s\n", a[i].age, a[i].name.c_str());
}

 

구조체를 만들어 index(순서), 나이, 이름을 객체화했다.

그리고 회원의 수를 입력 받고 그 수만큼 구조체 배열을 만들어줬다.

그 값을 입력받고 compare를 통해서 나이가 같은 경우에는 index 순서대로, 아닌 경우에는 나이가 적은 순서대로 정렬하게 해 줬다.

그리고 시간 초과 때문에 출력은 printf를 사용했다.

 

2) 두 번째 방법

 

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

using namespace std;

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

int main()
{
    int n, i ,a;
    string s;
    vector<pair<int, string>> v;

    cin >> n;

    for (i = 0; i < n; i++)
    {
        cin >> a >> s;
        v.push_back(make_pair(a, s));
    }

    stable_sort(v.begin(), v.end(), compare);

    for (i = 0; i < n; i++)
        printf("%d %s\n", v[i].first, v[i].second.c_str());
}

 

페어로 나이와 이름을 벡터에 저장한다. 

그리고 stable_sort로 정렬하며, compare로 나이가 적은 순서대로 정렬할 수 있게 해 준다.

출력은 역시 printf를 썼는데 퀵 소트가 아니라 머지 소트라서 그런지 메모리를 많이 썼다....