[BOJ] 10804 - 나이순 정렬

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

10814번: 나이순 정렬

 

문제풀이

 

커스텀 정렬문제이다. endl;를 사용하면 시간초과가 났으나, "\n"를 사용한 후 통과했다.

 

통과 코드1

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

bool comp(const vector<int> &v1, const vector<int> &v2)
{
    if (v1[0] < v2[0])
        return true;
    else if (v1[0] > v2[0])
        return false;
    else
    {
        if (v1[1] < v2[1])
            return true;
        else
            return false;
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int n;
    cin >> n;

    int a;
    string b;
    vector<vector<int> > v; // index age
    vector<string> v2;      // name
    for (int i = 0; i < n; i++)
    {
        cin >> a;
        cin >> b;
        vector<int> vv;
        vv.push_back(a);
        vv.push_back(i);
        v.push_back(vv);

        v2.push_back(b);
    }

    sort(v.begin(), v.end(), comp);
    for (int i = 0; i < v.size(); i++)
    {
        int index = v[i][1];
        cout << v[i][0] << " " << v2[index] << "\n";
    }
}

아래는 속도가 개선된 코드. 가입한 순서로 주어진다는 특징을 활용한 코드이다.

 

통과 코드2

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

int main(void)
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int n;
    cin >> n;

    int age;
    string name;
    vector<string> v[201];
    for (int i = 0; i < n; i++)
    {
        cin >> age >> name;
        v[age].push_back(name);
    }

    for (int i = 1; i <= 200; i++)
    {
        if (v[i].size() == 0)
            continue;

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

 

주의할 점

cin은 띄어쓰기를 기준으로 입력받는다. 

1 2 를 입력 받기 위해서는  cin << a << b; 를 사용하면 된다.

 

띄어쓰기를 기준으로 입력받기 때문에, 공백포함 string을 입력받기 위해서는 

getline(cin, a); 를 사용하면 된다.