[백준] 10814번: 나이순 정렬

 

---

 

문제

https://www.acmicpc.net/problem/10814

 

 

개념

정렬

 

 

실행 결과

 

 

 

 

 

구현 코드(c++)

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

// 정렬 기준 - 나이 오름차순
bool comp(const pair<int, string>& a, const pair<int, string>& b) {
  return a.first < b.first;
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);

  int n;
  cin >> n;
  vector<pair<int, string>> arr(n);

  for (int i = 0; i < n; i++) {
    cin >> arr[i].first >> arr[i].second;
  }

  // 안정적인 정렬 사용
  stable_sort(arr.begin(), arr.end(), comp);

  for (const auto& member : arr) {
    cout << member.first << " " << member.second << "\n";
  }

  return 0;
}

 

 

 

 

코드 설명

먼저 나는 일반 sort 함수를 사용했다가 틀린 문제임을 밝힌다.

그러면 이 문제에서 왜 sort가 아니라 stable sort를 사용해야 할까?

 

stable sort란?

 

이름 그대로 안정적인 정렬로, c++의 표준 라이브러리로 제공된다.

이는 정렬 기준이 동일한 원소들끼리 입력에서의 상대적인 순서를 보장하는 정렬이다.

 

문제에서 주어진 조건에서 나이가 같으면 가입한 순으로 이름을 출력해야 한다고 한다.

즉, pair<int, string>에소 int는 오름차순, string은 입력 순으로 정렬해야 하는 것이다.

만약 일반적인 sort를 사용한다면 int가 같은 경우 정렬 기준이 동일하므로, 뒤에 있는 string에 대한 상대적인 순서를 보장할 수 없다.

따라서 이를 보장하기 위해 가입순서와 같은 정렬 기준이 필요할때는 stable sort를 사용한다.

 

안정 적렬에는 insert, merge, bubble 등의 종류가 있다. 

algorithm 헤더의 stable sort는 merge sort를 기반으로 한다.

따라서 나는 comp 함수로 나이순 오름차순을 선언하고, stable sort로 가입순서를 보장하도록 설계했다.

 

 

 

 

---

 

참고 자료 

https://www.baeldung.com/cs/stable-sorting-algorithms

C++ 레퍼런스 - std::stable_sort (<algorithm>)