#51. [백준_C언어] 1181 : 단어 정렬

 

 입력 코드 

#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;
}

 

 

 코드 설명 

#정렬 #문자열

 

정렬 알고리즘을 이용해서 문자열 길이를 비교하고, 문자열 길이가 같을 때에는 사전식 배열을 해야 하는데

 

정렬 알고리즘 중에서 뭘 사용해야 할지도 뭐가 있는지도 모르겠고, 어떤 라이브러리를 추가해야 할지도 모르겠다. 

 

그래서 우선 참고할 만한 링크들만 걸어놓고 개념부터 정리하고 나중에 다시 풀어야겠다.

 

 

 합병 정렬 

gmlwjd9405.github.io/2018/05/08/algorithm-merge-sort.html

[알고리즘] 합병 정렬(merge sort)이란 - Heee's Development Blog

 

 

↓↓↓ 참고한 사이트

blog.naver.com/vjhh0712v/221466947001

백준 알고리즘 1181번 문제풀이

daydreamx.tistory.com/entry/baekjoon1181

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

h32j00.tistory.com/33

[백준 1181] 단어 정렬

 

 

 

 문제 출처 

www.acmicpc.net/problem/1181

1181번: 단어 정렬