[백준] 10814번: 나이순 정렬 C++로 풀어보기

10814번 설명

생각

구조체를 사용해서 풀면 될 것 같다.

 

문제를 풀 때 시행착오를 겪었는데,

 

처음에는 struct s s1[100005]로 구조체 배열을 선언했었는데, 그러면 코드가 잘 실행되지 않는다.

-> 스택 오버플로우가 발생하기 때문! 구조체 배열을 동적 할당하자.

 

그리고 정렬을 할 때 그냥 sort를 썼었는데, 그냥 sort를 쓰면 동일한 우선순위를 가진 원소들 사이의 상대적인 순서가 보존되지 않는다. 

-> sort가 아닌 stable_sort를 써야한다.

 

코드

#include <bits/stdc++.h>
using namespace std;

struct s { // 구조체 선언
    int age;
    string name;
};

bool compare(const s& s1, const s& s2) { // 나이가 적은 순서대로 정렬
    return s1.age < s2.age;
}

int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    int n;
    cin >> n;

    struct s* st = new struct s[n]; // 동적으로 구조체 배열 할당
    // 동적으로 할당한 배열은 스택이 아닌 힙 메모리를 사용하므로
    // 스택의 크기 제한을 초과할 걱정이 없어도 된다.
 

    for (int i = 0; i < n; i++) { // 나이와 이름 입력
        cin >> st[i].age;
        cin >> st[i].name;
    }

    // stable_sort를 사용해야 동일한 우선순위를 가진 원소들 사이의 상대적인 순서가 보존된다.
    stable_sort(st, st + n, compare);

    for (int i = 0; i < n; i++) { // 출력
        cout << st[i].age << " " << st[i].name << "\n";
    }
    
    delete[] st; //동적 할당 해제
}

 

결과

10814번 결과

사실 구조체를 많이 써본 적이 없었는데 이번 문제를 통해 구조체에 더욱 익숙해질 수 있었다.

그리고 STL sort는 비교 함수를 내가 정해서 넘겨줄 수 있다는 것을 기억하자!