백준 10814번 : 나이순 정렬 (C++) (stable_sort 이용)
2021. 5. 14. 15:39
https://www.acmicpc.net/problem/10814
10814번: 나이순 정렬
온라인 저지에 가입한 사람들의 나이와 이름이 가입한 순서대로 주어진다. 이때, 회원들을 나이가 증가하는 순으로, 나이가 같으면 먼저 가입한 사람이 앞에 오는 순서로 정렬하는 프로그램을
www.acmicpc.net
코드
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
|
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
bool cmp(pair<int,string> a,pair<int,string> b)
{
if(a.first<b.first)
return true;
else
return false;
}
int main() {
int n,t;
string str;
cin>>n;
vector<pair<int,string>> arr;
for(int i=0;i<n;i++)
{
cin>>t;
cin>>str;
arr.push_back({t,str});
}
stable_sort(arr.begin(),arr.end(),cmp);
for(int i=0;i<n;i++)
{
cout<<arr[i].first<<" "<<arr[i].second<<"\n";
}
return 0;
}
|
cs |
풀이
나이순대로 정렬하면서 나이가 같을 때는 입력받은 순서를 유지해주는 문제이다. sort함수는 quicksort로 구현되어 있어서 나이순대로 정렬하면서 입력받은 데이터의 순서가 뒤바뀔 수 있는데 stable_sort는 mergesort로 구현되어 있어서 나이순대로 정렬해도 입력받은 데이터의 순서가 뒤바뀌지 않는다고 한다. 따라서 stable_sort로 입력받은 데이터들을 정렬하면 문제를 해결할 수 있다.
stable_sort의 사용 방법은 일반 sort 함수와 같이 stable_sort(arr.begin(),arr.end()) 배열,벡터등의 시작주소 값, 끝 주소 값을 전달해서 사용할 수 있고 위의 코드에서처럼 정렬기준에 따라 true ,false를 리턴하는 정렬함수를 만들어서 사용할 수 있다.
'알고리즘 > 백준' 카테고리의 다른 글
| 백준 9466번 : 텀 프로젝트 (C++) (0) | 2021.05.27 |
|---|---|
| 백준 11576번 : Base Conversion (C++) (0) | 2021.05.26 |
| 백준 11650번 : 좌표 정렬하기 (C++) (0) | 2021.05.14 |
| 백준 2446, 10991, 10992번 : 별찍기-9, 별찍기-16, 별찍기-17 (C++) (0) | 2021.05.12 |
| 백준 1373번 : 2진수 8진수 (C++) (0) | 2021.03.28 |
