(백준 10814) 나이순 정렬

문제

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

잘못된 방법

처음에는 그냥 순회를 통해서 두번 정렬을 행하는것으로 했지만,

시간 초과가 나와서 해결방법을 고민하다가 정답을 봣다.

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

using namespace std;

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

int main()
{
    int n;
    cin >> n;
    int age;
    string name;
    vector<pair<int, string>> sub;
    for (int a = 0; a < n; a++)
    {
        cin >> age >> name;
        sub.push_back(make_pair(age, name));
    }
    sort(sub.begin(), sub.end());
    for (int a = 1; a < n; a++)
    {
        if (sub[a - 1].first == sub[a].first)
        {
            sort(sub.begin(), sub.end(), comapare1);
        }
    }
    for (int a = 0; a < n; a++)
    {
        cout << sub[a].first << sub[a].second << endl;
    }
}

보니까 for문 안에서 소팅을 해버려서 무조건 타임오버가 날수밖에 없는 구조였음.

 

정답코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>

using namespace std;

bool cmp (pair<int, string> u, pair<int, string> v)
{
return u.first < v.first;
}

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

    vector<pair<int, string>> vec(T);

    for (int i = 0; i < T; i++)
        cin >> vec[i].first >> vec[i].second;

    stable_sort(vec.begin(), vec.end(), cmp);

    for (int i = 0; i < T; i++)
        cout << vec[i].first << " " << vec[i].second << "\n";

}

utility에 존재하는 stable_sort라는것을 사용해서 문제를 해결했고, 이외에도 다양하게 문제를 해결하는 방법이 있었다.

그중에서 내가 항상하는 구조체를 만드는 방법도 존재를해서 살짝 기분이 좋앗다.