[C++] 백준 10814번 - 나이순 정렬

문제

온라인 저지에 가입한 사람들의 나이와 이름이 가입한 순서대로 주어진다. 이때, 회원들을 나이가 증가하는 순으로, 나이가 같으면 먼저 가입한 사람이 앞에 오는 순서로 정렬하는 프로그램을 작성하시오.

입력

첫째 줄에 온라인 저지 회원의 수 N이 주어진다. (1 ≤ N ≤ 100,000)
둘째 줄부터 N개의 줄에는 각 회원의 나이와 이름이 공백으로 구분되어 주어진다. 나이는 1보다 크거나 같으며, 200보다 작거나 같은 정수이고, 이름은 알파벳 대소문자로 이루어져 있고, 길이가 100보다 작거나 같은 문자열이다. 입력은 가입한 순서로 주어진다.

출력

첫째 줄부터 총 N개의 줄에 걸쳐 온라인 저지 회원을 나이 순, 나이가 같으면 가입한 순으로 한 줄에 한 명씩 나이와 이름을 공백으로 구분해 출력한다.

접근

#define _CRT_SECURE_NO_WARNINGS
#include <iostream> 
#include <algorithm>
#include <string>
#include <vector>
#include <math.h>
#include <cmath>
#include <cstring>
using namespace std;

int age[100000] = {};
string name[100000] = {};

int main() {

    int n;
    scanf("%d ", &n);

    for (int i = 0; i < n; i++) {
        scanf("%d", &age[i]);
        cin >> name[i];
    }


    for (int i = 1; i < n; i++) {
        int age_key = age[i];
        string name_key = name[i];

        int j = i - 1;

        while (j >= 0 && age[j] > age_key) {
            age[j + 1] = age[j]; 
            name[j + 1] = name[j];
            j--;
        }
        age[j + 1] = age_key;
        name[j + 1] = name_key;

    }

    for (int i = 0; i < n; i++) {
        printf("%d ", age[i]);
        cout << name[i] << "\n";
    }


    return 0;
}

선택정렬을 이용햇 풀었는데 시간초과가 났다 ㅋㅋ

알고보니 지금 내가 이용한 알고리즘은 삽입정렬인데 삽입 정렬의 시간 복잡도는 O(N^2)이다

그래서 시간초과가 난것이다 N이 최대 10만이므로 O(100억)이다 

그래서 이보다 더 좋은(O(NlogN)) 정렬 방법으로 문제를 해결해야 하는 것이다 

 

코드

#define _CRT_SECURE_NO_WARNINGS
#include <iostream> 
#include <algorithm>
#include <string>
#include <vector>
#include <math.h>
#include <cmath>
#include <cstring>
using namespace std;


struct MyStruct
{
    int age;
    string name;
};


bool compare(const MyStruct& fir, const MyStruct& sec) {
    if (fir.age != sec.age) { //나이가 다르면
        return fir.age < sec.age; //나이가 적은 사람부터 
    }
    return false;
} 


int main() {

    int n;
    scanf("%d ", &n);

    vector<MyStruct> str(n);

    for (int i = 0; i < n; i++) {
        cin >> str[i].age >> str[i].name;
    }

    stable_sort(str.begin(), str.end(),compare);

    for (int i = 0; i < n; i++) {
        cout << str[i].age << " " <<  str[i].name <<"\n";
    }


    return 0;
}

리뷰

일단 내가 직접 정렬을 구현하지 않고 c++의 내장함수인 sort함수를 사용해야겠다고 생각했다

이 함수를 직접 써본적은 없어서 좀 알아보다가 비슷한 정렬함수인 stable_sort함수를 알게되었다

우선 두 함수의 공통점은 모두 내부 원소를 정렬하는 함수이다 

하지만 동작방식에는 차이가 있는데

sort함수 : 퀵소트(quick sort) 알고리즘을 사용하여 정렬한다. 이는 일반적으로 빠르지만, 안정적인 정렬을 보장하지 않는다. 즉, 원래의 요소들의 상대적인 순서가 보존되지 않을 수 있다

stable_sort함수 : 안정적인 정렬을 보장한다. 먼저 요소들을 정렬하고, 같은 값이 있을 경우에는 원래의 순서를 보존하며 정렬한다. 이를 위해 일반적으로 머지소트(merge sort) 알고리즘을 사용한다

 

그러니까 sort함수는 불안정한 함수이고 stable_sort는 안정적인 함수이다

 

예를 들어 {5,2 9,8 1,5} 라는 배열을 정렬하고자 한다면

{1,2,5,5,8,9}이렇게 정렬이 된다

근데 중요한건 sort함수에서는 5는 같은 숫자이지만 5,5이 순서대로 정렬이될수도 있다 그래서 불안정한 함수라고 하는것이다

반면에 stable_sort는 원래의 순서를 보존해준다 

 

이 문제는 stable_sort를 써야한다 왜냐면 예시를 보면 알 수 있듯이 나이가 같은 경우가 있으면 가입순서대로 정렬해야한다 그러니까 원래 순서를 보존해야하기 때문에 이 함수를 쓴다!!

 

1.stable_sort함수를 쓸 때는 보통 클래스나 구조체를 사용한다고한다 그래서 나이와 이름을 담는 구조체를 만들었다 그리고 이 구조체를 객체로가지는? 벡터를 선언했다

 

2. 나이와 이름을 입력받고

 

3. stable_sort함수를 써서 정렬한다이 함수는 세개의 인자를 받는데 첫번째 인자는 정렬할 벡터나 배열의 시작 주소를 가리키는 포인터, 두번째 인자는 정렬할 벡터나 배열의 끝 주소를 가리키는 포인터, 세 번째 인자는 정렬 기준을 정의하는 함수 포인터이고 이 함수 포인터는 두 개의 인자를 받아서 두 원소를 비교하여 정렬기준을 결정한다

 

4. compare함수를 만들어서 두원소를 비교하는 함수를 정의했다bool함수를 썼는데

구조체의 인스턴스를 받아서 먼저 if문의 조건문을 확인한다 결과가 true이면 fir.age, sec.age를 비교한다 서로 나이가 다른경우에는 fir가 sec보다 작을때 true를 반환한다 그래서 나이가 작은 순으로 출력된다 

그리고 return false는 false를 반환한다는 것이다 그니까 if문의 결과가 거짓이라는건데 fir.age == sec.age인 경우이다 이때는 그냥 false를 반환하고 정렬을 안한다 그래서 가입순서가 유지되고 그대로 출력된다

생각보다 생각해야할 것도 많고 좀 어려웠다 그리고 새로운 함수도 알게되엇다! ㅋ

출처

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