[백준] 10814 나이순 정렬 C++ (정렬)

📌 백준 10814 나이순 정렬
https://www.acmicpc.net/problem/10814

이 문제는 두 가지 방법으로 풀었다.
답을 제출하면 계속 틀렸습니다가 나왔고 내가 무슨 부분을 놓치고 있는지 잘 모르겠더라. 그래서 고민 끝에 질문 게시판에 처음으로 글을 올렸고 어떤 천사 같은 분이 도움을 주셨다. 감사합니다 🙇‍♀️

내가 놓치고 있었던 부분은
조건을 하나 걸어주지 않았던 것이다. 정확히 말하면 sort()를 모르고 썼다.

이 문제를 풀 때 고려해줘야하는 조건은 2개다.
1. 나이 순으로 정렬한다.
2. 나이가 같으면 가입한 순으로 정렬한다.

오류가 났던 코드는 배열에 입력 값을 저장하고 sort()로 나이 순서대로 정렬했다. sort()를 쓰면 나이 순서대로 정렬 되고 같은 나이면 입력한 순서대로 출력하는줄 알았다.

그러나 그것은 아주 큰 오해

sort()는 배열의 두 원소를 비교하는 도구로 사용된다.
그런데 배열의 원소가 한 개가 아니라 지금처럼 여러 개로 묶여있다면?
배열의 x좌표를 주루룩 정렬했다고 치자. 만약 x좌표가 같은 것들이 있을 때, y좌표는 어떤 순서로 정렬될까?

sort()는 첫 번째 원소가 같을 경우, 두 번째 원소의 입력 순서대로 출력한다는 보장이 없다. 그래서 예측이 불가능한 불안정 정렬이다.
그럼 나머지 원소들을 입력 순서대로 출력하려면 어떻게 해야할까. 방법은 2가지다.

1. sort() 비교 함수(compare) 내에 조건을 추가해준다.
   멤버 변수로 idx를 추가해주었다. 나이가 같을 경우, idx를 오름차순으로 정렬하도록 했다.
2. stable_sort() 를 사용한다.
   stable_sort()는 sort()와 비슷하지만 다른 정렬 도구다.
   첫 번째 원소가 같을 경우, 두 번째 원소의 입력 순서대로 출력을 보장한다. 즉 동일한 값에 대해 기존 순서가 보장되는, 예측할 수 있는 안정적인 정렬이다.

sort()

• 첫 번째 원소가 같을 경우, 두 번째 원소의 입력 순서대로 출력한다는 보장이 없다.
• 동일한 값에 대해 기존 순서가 뒤바뀔 수 있다.
• 예측이 불가능한 불안정 정렬

stable_sort()

• 첫 번째 원소가 같을 경우, 두 번째 원소의 입력 순서대로 출력을 보장한다.
• 동일한 값에 대해 기존 순서가 보장된다.
• 예측 가능한 안정적 정렬

그래서 여기서는 나이 순서대로 정렬하고 나이가 같으면 입력 순서대로 받기 위해 stable_sort()를 사용했다. 사용법은 sort()와 동일하다.

비교함수에 조건 추가

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

struct person
{
    int age, idx;
    string name; //int로 바꿔주면 오류 안남
};

bool compare(const person& now, const person& last)
{
    if(now.age != last.age) return now.age < last.age;
    return now.idx < last.idx;
}

int main()
{	
    ios::sync_with_stdio(false);
	cin.tie(NULL);

    int N;
    cin >> N;
    person people[100001]; //구조체 배열

    for (int i = 0; i < N; i++) //배열에 값 넣어줌
    {    
        cin >> people[i].age >> people[i].name;
        people[i].idx = i;
    }

    //정렬
    //stable_sort(people, people + N, compare);
    sort(people, people + N, compare);

    //답 출력
    for (int i = 0; i < N; i++)
        cout << people[i].age << " " << people[i].name << "\n";
}

stable_sort() 사용

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

struct person
{
    int age;
    string name; //int로 바꿔주면 오류 안남
};

bool compare(const person& now, const person& last)
{
    if(now.age != last.age) return now.age < last.age;
    return false;
}

int main()
{	
    ios::sync_with_stdio(false);
	cin.tie(NULL);

    int N;
    cin >> N;
    person people[100001]; //구조체 배열

    for (int i = 0; i < N; i++) //배열에 값 넣어줌
        cin >> people[i].age >> people[i].name;

    //정렬
    stable_sort(people, people + N, compare);

    //답 출력
    for (int i = 0; i < N; i++)
        cout << people[i].age << " " << people[i].name << "\n";
}