Algorithm/문제풀이
[C++] 백준 알고리즘 10814 나이순 정렬
사과당근
2022. 2. 25. 21:48
10814번: 나이순 정렬
온라인 저지에 가입한 사람들의 나이와 이름이 가입한 순서대로 주어진다. 이때, 회원들을 나이가 증가하는 순으로, 나이가 같으면 먼저 가입한 사람이 앞에 오는 순서로 정렬하는 프로그램을
www.acmicpc.net
두가지 값을 저장하는 것이므로 pair를 이용하면 된다.
단, 첫 번째 값인 나이순으로 정렬하되 두 번째 값인 이름은 입력 순서를 유지해야한다.
#include<algorithm> 안에 있는 sort 함수를 써서 정렬을 했다
계속 틀렸습니다가 떠서 당황했는데, 알아본 결과 sort의 경우 비교하는 값이 같을 경우에 원래 순서를 유지한다는 보장이 없다고 한다. 다시 말해 sort로 정렬하면 나이가 같은 사람들은 정렬 순서가 원래와 다르게 바뀔 수도 있다는 것이다.
stable_sort를 이용하면 정렬되지 않은 데이터는 원래 순서를 유지하며 정렬을 한다고 한다.
4%에서 '틀렸습니다'가 계속 나올 경우, sort가 아닌 stable_sort를 이용해보자
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
bool cmp (pair<int, string> a, pair<int, string> b) {
return a.first<b.first;
}
int main(){
int n;
cin>>n;
vector<pair<int, string>> person(n);
for(int i=0; i<n; i++)
cin>>person[i].first>>person[i].second;
//sort 함수 사용시 '틀렸습니다'
stable_sort(person.begin(),person.end(),cmp);
for(int i=0; i<n; i++)
cout<<person[i].first<<' '<<person[i].second<<'\n';
}