[백준 10814] 나이순 정렬

🔗문제 풀러가기
단계별로 풀어보기 단계 13의 10번째 문제이다.

문제 분석

첫 번째 원소가 같을 경우, 두 번째 원소의 입력 순서대로 출력을 보장하는 stable_sort()를 이용해 문제를 해결하였다.

코드

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
bool compare(pair<int, string> a, pair<int, string> b)
{
	return a.first < b.first;
}

int main()
{
	int n;

	cin >> n;

	pair<int, string> temp;
	vector<pair<int, string>> vec;

	for (int i = 0; i < n; i++)
	{
		cin >> temp.first >> temp.second;
		vec.push_back(temp);
	}

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

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

}

해석

1. int와 string으로 되어있는 pair형 temp를 입력받아 벡터에 저장한다.
2. 첫 번째 원소가 같을 경우, 두 번째 원소의 입력 순서대로 출력을 보장하는 stable_sort을 이용해 정렬한뒤 차례대로 출력 하면 끝!

sort()

• 두가지 원소가 들어올 경우
  첫 번째 원소가 같을 때, 두 번째 원소의 입력 순서대로 출력한다는 보장이 없어 동일한 값에 대해 기존 순서가 뒤바뀔 수 있는 예측이 불가능한 불안정 정렬이다

stable_sort()

• 두가지 원소가 들어올 경우,
  첫 번째 원소가 같을 때, 두 번째 원소의 입력 순서대로 출력을 보장한다. 때문에 동일한 값에 대해 기존 순서가 뒤바뀌지 않는 예측이 가능한 안정 정렬이다