백준 10814번 [나이순 정렬](C++)-yes6686- 티스토리

백준 문제 풀이: 10814 [나이순 정렬]

---

문제 링크: https://www.acmicpc.net/problem/10814

문제 설명:

회원들의 나이와 이름이 주어질 때, 나이가 증가하는 순서대로 정렬하는 문제입니다. 나이가 같을 경우, 입력된 순서를 유지해야 합니다. 이를 위해 **안정 정렬(stable sort)**을 사용해야 합니다.

---

문제 해결 코드

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
vector<pair<int, string>>v;

bool compare(pair<int, string> a, pair<int, string> b) {
    return a.first < b.first;
}

int main() {
    int n;
    cin >> n;
    int a;
    string b;
    for (int i = 0; i < n; i++) {
        cin >> a >> b;
        v.push_back(make_pair(a, b));
    }
    stable_sort(v.begin(), v.end(), compare);
    for (int i = 0; i < n; i++) {
        cout << v[i].first << ' ' << v[i].second << '\n';
    }
}

---

코드 설명

• 핵심 알고리즘: 안정 정렬(stable_sort)을 사용하여 나이를 기준으로 정렬
• 구현 세부사항:
  • stable_sort 함수는 나이가 같은 경우, 입력된 순서를 유지합니다.
  • 정렬의 기준은 pair의 첫 번째 요소(나이)입니다.
  • 입력 데이터를 vector<pair<int, string>>에 저장한 후, 안정 정렬을 수행합니다.
• 시간 복잡도: O(n log n)
  • 입력 데이터 저장: O(n)
  • 안정 정렬: O(n log n)

---

결과

회원들의 나이와 이름을 안정 정렬을 사용하여 요구 조건에 맞게 정렬했습니다. 입력된 순서가 유지되며, 나이순으로 정렬된 결과를 출력합니다.

다른 접근 방식이나 개선 사항이 있다면 댓글로 공유 부탁드립니다!