[백준/C언어] 10814번 - 나이순 정렬

백준 웹사이트 "10814번 - 나이순 정렬" 문제풀이입니다.

언어는 C언어입니다. (제출 언어: C99)

 

---

문제

10814번: 나이순 정렬

---

소스 코드

#include <stdio.h>
#include <string.h>

void merge_sort(int *arr, char (*name)[101], int index, int len);
void merge(int *arr, char (*name)[101], int l_index, int r_index, int l_len, int r_len);

int main(void){
    int N;
    scanf("%d", &N);

    int age[N];
    char name[N][101];

    for(int i=0; i<N; i++){
        scanf("%d %s", &age[i], name[i]);

    }
    merge_sort(age, name, 0, N);

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

void merge_sort(int *arr, char (*name)[101], int index, int len){
    // Base Case
    if(len==1){
        return;
    }

    // Recursive Case
    // 1. arr을 반으로 나눈다
    int left = index;
    int right = index + len/2;
    int left_len = len/2;
    int right_len = len - len/2;

    // 2. 왼쪽, 오른쪽을 각각 merge_sort 한다
    merge_sort(arr, name, left, left_len);
    merge_sort(arr, name, right, right_len);

    // 3. 왼쪽, 오른쪽을 merge 한다
    merge(arr, name, left, right, left_len, right_len);
}

void merge(int *arr, char (*name)[101], int l_index, int r_index, int l_len, int r_len){
    // 1. 임시 배열 선언
    int temp[l_len+r_len];
    char temp_name[l_len+r_len][101];
    int count = 0;
    
    // 2. 왼쪽, 오른쪽의 가장 작은 수 비교
    int l_count = 0;
    int r_count = 0;
    while(1){
        int left = l_index + l_count;
        int right = r_index + r_count;
        //arr[left] <= arr[right] 사용 -> stable sort
        if(arr[left] <= arr[right]){
            temp[count] = arr[left];
            strcpy(temp_name[count], name[left]);
            count++;
            l_count++;
        }
        else{
            temp[count] = arr[right];
            strcpy(temp_name[count], name[right]);
            count++;
            r_count++;
        }

    // 3. 왼쪽이나 오른쪽의 끝에 도달하면 break
        if(l_count==l_len || r_count==r_len){
            break;
        }
    }

    // 4. 남은 요소 temp로 복사
    if(l_count==l_len){ // 오른쪽을 복사
        while(count<l_len+r_len){
            temp[count] = arr[r_index+r_count];
            strcpy(temp_name[count], name[r_index+r_count]);
            count++;
            r_count++;
        }
    }
    else{               // 왼쪽을 복사
        while(count<l_len+r_len){
            temp[count] = arr[l_index+l_count];
            strcpy(temp_name[count], name[l_index+l_count]);
            count++;
            l_count++;
        }
    }

    // 5. arr에 임시배열 복사
    for(int i=l_index; i<l_index+l_len+r_len; i++){
        arr[i] = temp[i-l_index];
        strcpy(name[i], temp_name[i-l_index]);
    }
}

---

문제 풀이

  정렬은 크기가 서로 다른 원소들을 크기 순서대로 정리하는 과정입니다. 하지만 두 원소의 크기가 같다면, 어떻게 정렬해야 할까요? 크기가 같은 두 원소의 순서가 입력 순서와 같은 정렬을 Stable Sort (안정 정렬)이라고 하고, 그렇지 않은 정렬을 Unstable Sort (불안정 정렬)이라고 합니다. 이번 문제의 핵심은 Stable Sort를 구현하는 것입니다.

  이전 문제들처럼, \(O(n^2)\) 시간 복잡도의 정렬 알고리즘을 사용하면 시간 초과가 걸릴 위험이 있기에 \(O(nlogn)\)의 시간 복잡도를 가지는 Merge Sort (병합 정렬)을 사용합니다. 11650번 문제의 코드를 참고하여 'merge_sort'와 'merge' 함수를 이용하고, 문제에 맞게 수정합니다. 파라미터로 두 가지 배열을 받는다는 차이가 있는데, 나이를 기록한 배열 'age'와 이름을 기록한 배열 'name'을 같이 입력 받아야하기 때문입니다. 이때 실제 정렬은 int 배열인 age를 기준으로 하고, age 배열 요소들의 위치가 바뀔 때마다 name 배열 요소들의 위치도 대응되게 바뀌도록 합니다. 이렇게 하면 name을 참고하지 않고 나이 순으로 정렬시킬 수 있습니다.

  이번 문제의 핵심은 stable sort를 구현하는 것이라고 했죠? Stable sort는 단순히 Line 59의 기존 코드 arr[left] < arr[right]를 arr[left] <= arr[right]로 바꿈으로써 이룰 수 있습니다. 기존 arr[left] < arr[right]일 때는 arr[left] == arr[right]일 경우, Line 65의 else문으로 넘어가 나중에 입력된 배열 요소를 앞쪽에 배치시켰습니다. 즉, 기존에는 unstable sort를 사용하고 있었던 셈이죠. Stable sort에서는 arr[left] == arr[right]일 경우 먼저 입력된 배열 요소를 앞쪽에 배치시켜야 하기 때문에, arr[left] <= arr[right]로 수정해줍시다.

  아래는 백준 웹사이트 "11650번 - 좌표 정렬하기" 문제풀이 링크입니다. 이차원 배열의 병합 정렬에 대해 더 알아보고 싶으면 참고해주세요!

[백준/C언어] 11650번 - 좌표 정렬하기