[C] 백준 1181번: merge sort 구현하기

📎 백준 1181번 풀러 가기

1181번: 단어 정렬

문제

알파벳 소문자로 이루어진 N개의 단어가 들어오면 아래와 같은 조건에 따라 정렬하는 프로그램을 작성하시오.

1. 길이가 짧은 것부터
2. 길이가 같으면 사전 순으로

입력

첫째 줄에 단어의 개수 N이 주어진다. (1≤N≤20,000) 둘째 줄부터 N개의 줄에 걸쳐 알파벳 소문자로 이루어진 단어가 한 줄에 하나씩 주어진다. 주어지는 문자열의 길이는 50을 넘지 않는다.

출력

조건에 따라 정렬하여 단어들을 출력한다. 단, 같은 단어가 여러 번 입력된 경우에는 한 번씩만 출력한다.

---

엄청난 시행착오를 겪은 문제이다.

첫째는 문제를 제대로 읽지 않았기 때문이고, 둘째는 오타...!

 

아무튼 문제를 어떻게 풀었는지 설명해보자면

처음에는 qsort로 풀려고 했었는데, qsort는 최악의 경우 시간 복잡도가 $ O(n^2) $이 될 수 있기 때문에,

시간 복잡도가 $ O(nlogn) $인 merge sort로 구현을 해보기로 했다.

 

바로 어제, 알고리즘 강의 시간에서 merge sort에 대해 배우기도 했으니

복습도 할 겸 겸사겸사!😄

 

처음에, 2차원 배열을 동적 할당을 하고,

이 2차원 배열을 함수의 매개변수로 넘겨주고,

그 함수 내에서 또 다른 함수의 매개변수로 넘겨줘서

함수 내의 또다른 2차원 배열 동적 할당을 해서 이리저리 하려다 보니

정말 온갖 오류들을 보았다.

 

평소에는 Segmentation fault 나 Aborted: core dumped 정도를 봤었는데,

오늘은 malloc() 경고도 보고, ssd(stack smashing detected:*** stack smashing detected ***: terminated 도 봤다.

메모리 접근이 잘못된 것은 알겠는데, 위에서 설명했다시피

동적 할당에 2차원 배열에 매개변수... 이렇게 되니까 어디가 잘못된 건지 잘 모르겠는 거다.

 

그래서 뒤엎었다! 처음부터 다시!

 

근데 제대로 작동을 하는 것 같긴 한데, 뭔가 아웃풋이랑 다른 거다.

알고 보니, 문제를 제대로 읽지 않아서, 길이 부분을 빼먹었다🤣

 

그래서 구조체에 문자열의 길이를 저장하는 변수를 추가하고, 다시 결과를 보았는데

오오오잉. 또 다르다. 이번엔 중복된 문자열이 자꾸 출력되는 것이었다. 나는 이미 처리를 했는데!?

 

이것도 한참을 찾다가 발견했다.

if() 문의 바로 뒤에 세미콜론 ; 을 붙여버려서 조건 체크만 하고 if문이 끝나버린 것이었다.

이런 오류가 정말... 찾기 힘든 것 같다.

 

아무튼 수많은 수행 착오 끝에 첫 merge sort로 문제 풀기 완료!

---

아래는 내가 구현한 코드👇

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

typedef struct {
    char string[51];
    int length;
} str;

str sort[20001];

void merge(str* arr, int first, int mid, int last) {
    int i = first;
    int j = mid + 1;
    int k = first;

    while(i <= mid && j <= last) {
        if (arr[i].length < arr[j].length) {
            sort[k++] = arr[i++];
        } else if (arr[i].length > arr[j].length) {
            sort[k++] = arr[j++];
        } else {
            if (strcmp(arr[i].string, arr[j].string) < 0) {
                sort[k++] = arr[i++];
            }
            else {
                sort[k++] = arr[j++];
            }
        }
    }
    if (i > mid) {
        while (j <= last)
            sort[k++] = arr[j++];
    }
    else {
        while (i <= mid)
            sort[k++] = arr[i++];
    }
    for (k = first; k <= last; k++) 
        arr[k] = sort[k];
}

void mergesort(str* arr, int first, int last) {
    int mid;
    if (first < last) {
        mid = (first + last) / 2;
        mergesort(arr, first, mid);
        mergesort(arr, mid + 1, last);
        merge(arr, first, mid, last);
    }
}

int main(void)
{
    int N;
    scanf("%d", &N);
    str arr[N];

    for(int i = 0; i < N; i++) {
        scanf("%s", arr[i].string);
        arr[i].length = strlen(arr[i].string);
    }

    mergesort(arr, 0, N - 1);

    printf("%s\n", arr[0].string);
    for (int i = 1; i < N; i++) {
        if (strcmp(arr[i-1].string, arr[i].string) != 0)
            printf("%s\n", arr[i].string);
    }
    return 0;
}

---

✍새로 안 사실들

1. Merge sort는 divide and conquer의 방식을 활용한 정렬 방식으로, 

    시간 복잡도는 $ O(nlogn) $이다.