[C/C++] 백준 10814번 - 나이순 정렬 (안정 정렬, 불안정 정렬)

 

<클래스 멤버 변수를 이용한 코드>

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

class member
{
public:
	int age;
	string name;
};

member M[100001];

bool compare(member a, member b)
{
	return a.age < b.age;
}

int main()
{
	int N;
	cin >> N;

	for(int i = 0; i < N; i++)
	{
		cin >> M[i].age >> M[i].name;
	}

	stable_sort(M,M+N,compare);

	for (int i = 0; i < N; i++)
	{
		cout << M[i].age << " " << M[i].name << "\n";
	}
}

 

<vector 컨테이너를 이용한 코드>

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

using namespace std;

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

int main()
{
    int N;
    cin >> N;

    vector<pair<int, string>> v(N);

    for (int i = 0; i < N; i++)
        cin >> v[i].first >> v[i].second;

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

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

 

2차원 배열의 생성하여 첫 번째 원소로는 나이 두 번째 원소로는 이름을 저장한다. 하지만 문제 조건에서 나이가 같을 경우 먼저 가입한 순서로 정렬을 해야 하므로 일반적인 sort() 함수를 사용 시 원하는 결과가 나오지 않을 수 있다.

정렬의 안정적 특성은 "정렬이 되지 않은 상태에서 같은 값을 가진 원소들의 순서가 유지되는가" 이다. 이러한 기준에 따라서 정렬은 "안정 정렬"과 "불안정 정렬"을 나뉜다. 위의 문제에서는 안정 정렬의 조건이 필요하므로 stable_sort() 함수를 사용하여 풀이를 하였다.

 

 

 

www.acmicpc.net/problem/10814

10814번: 나이순 정렬