[백준/C언어] 1181번 - 단어 정렬

백준 웹사이트 "1181번 - 단어 정렬" 문제풀이입니다.

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

 

---

문제

1181번: 단어 정렬

---

소스 코드

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

void merge_sort(char (*arr)[51], int index, int len);
void merge(char (*arr)[51], int l_index, int r_index, int l_len, int r_len);
int compare(char (*a)[51], char (*b)[51]);

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

    char words[N][51];  //단어 저장
    for(int i=0; i<N; i++){
        scanf("%s", &words[i]);
    }

    merge_sort(words, 0, N);
    for(int i=0; i<N; i++){
        if(i>0 && !strcmp(words[i], words[i-1]))  //같으면 0 반환
            continue;
        printf("%s\n", words[i]);
    }
}

void merge_sort(char (*arr)[51], 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, left, left_len);
    merge_sort(arr, right, right_len);

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

void merge(char (*arr)[51], int l_index, int r_index, int l_len, int r_len){
    //printf("merge: %d %d\n", l_index, r_index);
    // 1. 임시 배열 선언
    char temp[l_len+r_len][51];
    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;
        if(compare(&arr[left], &arr[right])){ //arr[left] < arr[right]이면 1
            strcpy(temp[count], arr[left]);
            count++;
            l_count++;
        }
        else{
            strcpy(temp[count], arr[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){
            strcpy(temp[count], arr[r_index+r_count]);
            count++;
            r_count++;
        }
    }
    else{               // 왼쪽을 복사
        while(count<l_len+r_len){
            strcpy(temp[count], arr[l_index+l_count]);
            count++;
            l_count++;
        }
    }

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

int compare(char (*a)[51], char (*b)[51]){  //a<b이면 1 반환
    int a_len = strlen(*a);
    int b_len = strlen(*b);
    if(a_len<b_len){
        return 1;
    }
    else if(a_len==b_len){  //사전 순으로 정렬
        for(int i=0; i<a_len; i++){
            if((*a)[i]<(*b)[i])
                return 1;
            else if((*a)[i]>(*b)[i])
                return 0;
        }
    }
    return 0;
}

---

문제 풀이

  이번 문제 역시 시간 복잡도 \(O(nlogn)\)의 정렬을 이용해야 하기에, 이전 문제들에서 사용했던 병합 정렬 (Merge Sort)의 코드를 이용합니다. 11650번 문제의 'merge_sort', 'merge', 'compare' 함수를 참고하는데, 알파벳 소문자의 단어를 다루는 문제이므로 입력받는 배열 파라미터는 char (*)[51]으로 바꿉니다. 이에 따라 각 함수 내부도 적절하게 수정합니다. merge_sort에서는 변하는 것이 없지만, merge에서는 <string.h>의 'strcpy(dst, src)' 함수를 이용해 String을 복사합니다. 또한, compare 함수는 문제의 조건대로 영어 단어 간의 대소관계를 비교하는데, 우선적으로 단어의 길이를 비교하고 (Line 100), 길이가 같다면 사전적으로 비교합니다 (Line 103).

  수정 과정을 거쳐도, 병합 정렬의 알고리즘에는 변화가 없습니다. 바뀌는 것은 입력 받는 배열의 종류, 그리고 element의 대소관계를 판별하는 기준 뿐입니다. 결과적으로 코드를 돌려보면, \(O(nlogn)\) 시간 안에 성공적으로 정렬을 완료합니다. 마지막으로, 같은 단어가 여러 번 입력된 경우에는 한 번씩만 출력되게끔 하면 되는데, 이는 출력 단계에서 설정해줍니다. Line 19의 'strcmp' 함수는 입력된 두 String이 같으면 0을 반환하고, 다르면 1을 반환합니다. 이를 이용해 단어가 차례로 출력될 때, 이미 출력된 단어와 같다면 출력되지 않도록 합니다.

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

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