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

문제

온라인 저지에 가입한 사람들의 나이와 이름이 가입한 순서대로 주어진다. 이때, 회원들을 나이가 증가하는 순으로, 나이가 같으면 먼저 가입한 사람이 앞에 오는 순서로 정렬하는 프로그램을 작성하시오.

 

입력

첫째 줄에 온라인 저지 회원의 수 N이 주어진다. (1 ≤ N ≤ 100,000)

둘째 줄부터 N개의 줄에는 각 회원의 나이와 이름이 공백으로 구분되어 주어진다. 나이는 1보다 크거나 같으며, 200보다 작거나 같은 정수이고, 이름은 알파벳 대소문자로 이루어져 있고, 길이가 100보다 작거나 같은 문자열이다. 입력은 가입한 순서로 주어진다.

 

출력

첫째 줄부터 총 N개의 줄에 걸쳐 온라인 저지 회원을 나이 순, 나이가 같으면 가입한 순으로 한 줄에 한 명씩 나이와 이름을 공백으로 구분해 출력한다.

 

---

정렬 알고리즘을 사용하는 문제.

앞서 풀었던 문제들은 전부 병합 정렬로 풀었는데(추후 포스팅 예정), 코드도 길고 계속 같은 코드를 돌려쓰는 것이 영 마음에 안들어서 내장 함수를 한번 써보고 싶어 조금 구글링해서 algorithm 헤더에 내장된 stable_sort() 를 사용하여 풀었다.

이거 먼저 포스팅하는 이유는 풀고 좀 감명받아서...

 

회원을 나이 순, 나이가 같으면 가입한 순 으로 정렬해야하기 때문에 같은 나이일 경우 정렬을 하면서 퀵소트 같이 정렬 과정에서 순서가 바뀔 수 있는 불안정 정렬(unstable sort)이 아닌, 들어온 순서대로 정렬이 되는 안정 정렬(stable sort)을 사용해야 한다.

그렇기 때문에 sort()가 아닌 stable_sort() 를 사용한다.

나이와 이름을 번거롭게 구조체나 클래스를 통해 정의하지 않고 사용하기 위해 pair 클래스를 사용하였다.

 

이름을 string 클래스로 설정하여 불가피하게 scanf / printf 대신 cin / cout 을 사용하였는데 그래서 그런가 제출했더니 시간초과가 나더라.. 어떻게 해결해야되나 싶어 검색해봤더니 마지막에 값 출력해줄 때 줄바꿈으로 endl 대신 "\n"으로만 바꿔줘도 정답처리가 된다 하더라고?? 속는 셈 치고 그거 하나만 바꿔줬더니 이왜진.. 앞으로 유용하게 사용할 것 같다.

 

코드

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

using namespace std;

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

int main(void) {
    int n;
    scanf("%d", &n);
    vector<pair<int, string> > list(n);

    for(int i = 0; i < n; i++) {
        cin >> list[i].first >> list[i].second;
    }

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

    for(int i = 0; i < n; i++) {
        cout << list[i].first << " " << list[i].second << "\n";
    }
    return 0;
}