[코딩테스트]BJ10814 나이순 정렬 - C++

[문제]

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

[입력]

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

[출력]

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

[문제풀이]

algorithm헤더의 stable_sort를 알고 있다면 쉽게 풀 수 있는 문제이다.
stable_sort는 sort함수와는 다르게 순서를 보장해준다. 실제로 아래의 식에서

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

위 부분을 sort함수로 바꾼다면 기존의 순서는 바뀌고 a.first,b.first만을 sort한 결과가 나오게 된다.

[코드]

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

using namespace std; 

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

	int n; 
	vector <pair<int, string>>ppl_list;
	cin >> n; 
	
	for (int i = 0; i < n; i++) {
		int age;
		string name; 
		cin >> age >> name;
		ppl_list.push_back(make_pair(age, name));
	}

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

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