컴공댕이 공부일지
[ C++/cpp ] 백준 (10814 나이순 정렬) ⭐sort_stable 본문
728x90
백준 10814번 나이순 정렬
(실버 5)
https://www.acmicpc.net/problem/10814
(정답 코드)
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef pair<int,string> p;
bool cmp(const p &a, const p &b) {
// 나이순 정렬
if(a.first!=b.first) {
return a.first < b.first;
}
// 나이가 같으면 변화없이 그대로 !
else {
return false; // 원래 순서 유지 !
}
}
void sortUser(vector<p>& user) {
// 입력 순서를 보존하는 안정적인 정렬을 보장하는 sort_stable
stable_sort(user.begin(), user.end(), cmp);
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
// 입력
int n;
cin >> n;
int age;
string name;
vector <p> user;
while (n--) {
cin >> age >> name;
user.push_back(make_pair(age, name));
}
// 연산
sortUser(user);
// 출력
for (int i=0; i<user.size(); i++) {
cout << user[i].first << " " << user[i].second << '\n';
}
return 0;
}
나이가 같은 경우엔, 먼저 가입한, 즉 먼저 입력된 순서로 출력해야한다. 그런데 이 부분에서 오류가 있었다.
비교함수의 리턴값을 false로 하면, 정렬없이 원래 순서가 유지된다고 해서
입력 순서 그대로 변화가 없을 것으로 예상해 그렇게 비교함수를 작성해서 풀었는데 틀렸다..
질문게시판을 보니 sort_stable로 풀어야 맞다길래 그 부분만 수정하니 맞음 ...! 왜 인지 궁금해서 더 찾아보았다.
🔎 sort와 sort_stable의 차이
사실, std::sort 함수는 안정적인 정렬을 보장하지 않습니다. 따라서 같은 값에 대해 입력 순서를 유지하지 않을 수 있습니다. 그러나 C++11 이후로 std::sort 함수는 안정 정렬을 수행하는데, 이는 특정 구현에 따라 달라질 수 있습니다.
반면 std::stable_sort 함수는 항상 안정적인 정렬을 보장합니다. 이는 입력 순서를 보존하는 것을 의미합니다. 그러나 안정적인 정렬을 유지하면서도 일반적인 std::sort보다 성능면에서는 조금 더 느릴 수 있습니다.
따라서 입력 순서를 유지하면서 정렬을 수행하려면 std::stable_sort 함수를 사용해야 합니다. 이를 이용하여 코드를 수정하고 다시 제출하면 올바르게 작동할 것입니다.
챗 지피티 체고 :)..
728x90
'문제 풀이 > 코딩 문제 풀이 모음' 카테고리의 다른 글
[ C++/cpp ] 백준 (11268 절댓값 힙) ⭐자료구조, 우선순위 큐 (0) | 2024.03.28 |
---|---|
[ C++/cpp ] 백준 (2840 행운의 바퀴) ⭐구현, 시뮬레이션 💥💦 (4) | 2024.03.05 |
[ C++/cpp ] 백준 (11650 좌표 정렬하기) ⭐정렬, 비교함수 (0) | 2024.02.29 |
[ C++/cpp ] 백준 (15685 드래곤 커브) ⭐구현, 시뮬레이션 (56) | 2023.11.24 |
[ java ] 코드업 (1476 2차원 배열 빗금 채우기 3-1) (0) | 2023.06.10 |
Comments