10814번: 나이순 정렬

 

- 관련 사이트: https://www.acmicpc.net/problem/10814

10814번: 나이순 정렬

 

첫번째 나이 값을 기준으로 비교 함수를 정의하였다.

단, 첫번째 값이 같을 경우 순서가 변경되지 않아야 하므로 일반적인 sort 함수가 아닌, stable_sort 함수를 사용하였다.

 

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

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

int main()
{
	ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    int N, age;
    string name;
    vector<pair<int, string>> lst;
    
    cin >> N;
    for (int i = 0; i < N; i++)
    {
        cin >> age >> name;
        lst.push_back(make_pair(age, name));
    }
    
    stable_sort(lst.begin(), lst.end(), compare);
    
    for (int i = 0; i < N; i++)
        cout << lst[i].first << " " << lst[i].second << "\n";
    
    return 0;
}

- 메모리: 9848 KB

- 시간: 76 ms

- 코드 길이: 638 B

 

정렬이 아닌 나이에 해당되는 이름들을 저장하여 나이 순으로 출력해주는 방법도 존재한다.

이는 입력받는 나이가 고정되어 있기에 가능한 방법이다.

 

1) 입력 가능한 나이 만큼의 string 벡터 선언 = vector<string> lst[201]

2) 나이 위치에 이름 저장 = lst[age].push_back(name)

3) 순차적으로 나이에 저장되어 있는 이름 출력

 

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

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    int N, age;
    string name;
    vector<string> lst[201];
    
    cin >> N;
    for (int i = 0; i < N; i++)
    {
        cin >> age >> name;
        lst[age].push_back(name);
    }
    
    for (int age = 1; age < 201; age++)
        for (int i = 0; i < lst[age].size(); i++)
            cout << age << " " << lst[age][i] << "\n";
    
    return 0;
}

- 메모리: 6900 KB

- 시간: 32 ms

- 코드 길어: 494 B

 

출력하는 방식을 하나씩 출력이 아닌, 하나의 문자열로 만들어 한번에 출력하면 메모리는 상대적으로 더 소모되지만 시간이 더 단축되는 것을 확인할 수 있다.

 

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

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    int N, age;
    string name;
    vector<string> lst[201];
    
    cin >> N;
    for (int i = 0; i < N; i++)
    {
        cin >> age >> name;
        lst[age].push_back(name);
    }
    
    string result = "";
    for (int age = 1; age < 201; age++)
        for (int i = 0; i < lst[age].size(); i++)
            result += to_string(age) + " " + lst[age][i] + "\n";
    cout << result;
    return 0;
}

- 메모리: 8476 KB

- 시간: 24 ms

- 코드 길어: 546 B