오늘의 코딩#4

오늘은 이전에 풀던 좌표 정렬하기에 대한 풀이가 떠오르지 않아 다른 문제부터 풀려 했다.
그래서 선택한 문제가 단어 정렬 문제 였는데 같은 이유로 문제가 풀리지 않았다.

이 문제는 최대 20,000개의 단어를 입력 받아 길이가 짧은 단어부터, 길이가 같다면 사전 순으로 출력하는 문제이다.
20,000개 정도는 충분히 빠르게 연산할 거라 생각 했는데 생각보다 시간 복잡도가 컷나보다.

그래서 구글링을 좀 해봤는데 merge sort라는 방법이 있었다.
합병 정렬이라고 하는데 폰 노이만이 제안한 방법이라고 하더라.
인류 역사상 최고의 천재라는 폰 노이만이라는 이름을 보는 순간 신뢰도가 급 상승했다.

이 방법은 배열을 절반으로 나누는 것을 반복해 정렬하며 다시 합병하는 방식으로 진행된다.
그렇다 보니 상대적으로 시간 복잡도가 작은데 n log₂ n 이다
기존에 내가 사용했던 선택정렬 방식의 시간 복잡도가 n^2 임을 고려하면 확실히 작다.

이게 이렇게 보면 큰 차이가 안 나는 것처럼 보이는데 run-time을 보면 차이가 크다.
정수 60,000개를 정렬할때 선택정렬은 10.842초가 걸리고 병합정렬은 0.026초 정도 걸린다고 한다.

여튼 나는 이 문제를

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

void sort(char lst[][51], int left, int right, char sorted_lst[][51])
{
int mid = (right + left) / 2;
int i1 = left, i2 = mid + 1;
int i3 = left;
int num = right - left;

while (i1 <= mid && i2 <= right)
{
    if (strlen(lst[i1]) < strlen(lst[i2]))
        strcpy(sorted_lst[i3++], lst[i1++]);
    else if (strlen(lst[i1]) > strlen(lst[i2]))
        strcpy(sorted_lst[i3++], lst[i2++]);
    else
    {
        if (strcmp(lst[i1], lst[i2]) < 0)
            strcpy(sorted_lst[i3++], lst[i1++]);
        else
            strcpy(sorted_lst[i3++], lst[i2++]);
    }
}
while (i1 <= mid)
    strcpy(sorted_lst[i3++], lst[i1++]);
while (i2 <= right)
    strcpy(sorted_lst[i3++], lst[i2++]);
for (int i = 0; i <= num; i++)
{
    strcpy(lst[left + i], sorted_lst[left + i]);
}

}

void merge_sort(char lst[][51], int left, int right, char sorted_lst[][51])
{
int mid;

if (left < right)
{
    mid = (right + left) / 2;
    merge_sort(lst, left, mid, sorted_lst);
    merge_sort(lst, mid + 1, right, sorted_lst);
    sort(lst, left, right, sorted_lst);
}

}

int main(void)
{
int n, i;
char lst[20000][51] = {
0,
};
char sorted_lst[20000][51] = {
0,
};

scanf("%d", &n);
for (i = 0; i < n; i++)
    scanf("%s", lst[i]);
merge_sort(lst, 0, n - 1, sorted_lst);
for (i = 0; i < n; i++)
{
    while (i != n - 1 && strcmp(lst[i], lst[i + 1]) == 0)
        i++;
    printf("%s\n", lst[i]);
}
return (0);

}

이렇게 풀었다.
배열을 둘로 나눠 서로를 비교하며 더 작은 길이를 가지 것을 먼저 복사하는 행위를 재귀로 구현해 최소한의 크기(2개)부터 이 알고리즘이 시행되며 최종적으로는 전체를 정렬하도록 했다.

출력에서 같은게 있으면 출력하지 않도록 하라 해서 조건을 걸었다.
조건문에서 왼쪽을 먼저 판단하는 것을 이용해 segmentation fault를 방지했다.

내일은 이전에 못 풀었던 좌표 정렬하기 문제를 다시 풀어야겠다.