[백준 C언어] 1181. 단어 정렬

문제

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

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

입력

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

출력

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

 

나의 풀이

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

int cmp(const void* a, const void* b) {
    int len_a = strlen(a);
    int len_b = strlen(b);

    if (len_a == len_b) return strcmp(a, b); //단어 길이가 같으면 사전 순 정렬
    return len_a-len_b; //단어 길이가 다르면 짧은 순 정렬
}

int main(void) {

    int n;
    scanf("%d", &n);
    char *arr, *p;
    arr = (char*)malloc(sizeof(char) * n * 51);
    p = arr;
    for (int i = 0; i < n; i++) {
        scanf("%s", p);
        p += 51;
    }


    qsort(arr, n, 51, cmp);

    p = arr;

    for (int i = 0; i < n; i++) {
        if (strcmp(p,p+51)!=0) {
            printf("%s\n", p);
        }
        p += 51;
    }

    free(arr);
    free(p);
    return 0;
}

 

 qsort() 함수를 이용하여 정렬해주기 위해 cmp 함수를 하나 만들어주었다. 

문제의 '단어 길이순 정렬'이 없었더라면 strcmp만 사용해도 무방했겠지만 우리는 단어 길이순으로 정렬해야 하므로, 

strlen(문자열 길이 반환하는 함수)를 이용하여 비교 후 같으면 사전순(strcmp) 정렬,

다르면 길이순 정렬을 해 준다. 

만약 길이가 긴 순으로 정렬하고 싶다면 (len_a-len_b)*(-1)을 해주면 된다.

 

단어 개수의 최대치가 20,000개이고 문자열의 길이가 50이라면 

배열 선언 시 무조건 20,000*51의 메모리를 잡아먹어야 할 것이라는 생각에

최적화를 위해 동적 메모리를 사용했다.  

물론 동적 메모리를 할당하기 위한 소요도 있을 것이므로 비슷비슷할 수도 있겠지만... 

 

어쨌든 포인터 형태이기 때문에 scanf 등의 함수를 사용할 때 

다음 단어로 옮겨가기 위해서는 공백문자를 포함한 51을 포인터에 더해 주면 된다.

입력받은 문자열을 qsort로 정렬한 후, 출력 시 중복이 아닌 단어만 출력해주면 끝.