[C++] 백준 13단계 - 10814번 문제 (나이순 정렬)

문제설명

 

소스코드

sort() 이용(quick sort)

#include <iostream>
#include <algorithm>
using namespace std;
class name_age {
public:
	string name;
	int age;
	int idx;
	bool operator < (name_age& arr) { 
		if (this->age != arr.age) return this->age < arr.age;
		else return this->idx < arr.idx;
	}
};
int main()
{
	ios_base::sync_with_stdio(false); //표준 스트림 동기화 해제
	cin.tie(NULL); //입력과 출력 연결 끊기
	int N;
	cin >> N;
	name_age* arr = new name_age[N];
	for (int i = 0; i < N; ++i)
	{
		cin >> arr[i].age >> arr[i].name;
		arr[i].idx = i;
	}
	sort(arr, arr + N);
	for (int i = 0; i < N; ++i) cout << arr[i].age << " " << arr[i].name << '\n';
}

 

stable_sort() 이용(merge sort)

#include <iostream>
#include <algorithm>
using namespace std;
class name_age {
public:
	string name;
	int age;
};
bool compare(const name_age& a, const name_age& b) { 
	if (a.age != b.age) return a.age < b.age;
	else return false;
}
int main()
{
	ios_base::sync_with_stdio(false); //표준 스트림 동기화 해제
	cin.tie(NULL); //입력과 출력 연결 끊기
	int N;
	cin >> N;
	name_age* arr = new name_age[N];
	for (int i = 0; i < N; ++i) cin >> arr[i].age >> arr[i].name;
	stable_sort(arr, arr + N, compare);
	for (int i = 0; i < N; ++i) cout << arr[i].age << " " << arr[i].name << '\n';
}

 

설명

• sort() : 동일한 값의 요소들에 대해, 두 요소가 기존에 가지고 있던 순서를 보장하지 않는다.
  따라서 입력받은 순서를 기억해서 따로 정렬해야한다.(정렬 속도 상대적으로 빠름)
• stable_sort() : 동일한 값의 요소들에 대해, 두 요소가 기존에 가지고 있던 순서를 보장한다.
  따라서 입력받은 순서를 기억하고 따로 정렬할 필요가 없다. (정렬 속도 상대적으로 느림)