[C언어 연습문제]강좌 17. Sorting Array of Strings(함수포인터 활용)

문자열 배열의 정렬 - 입력된 단어를 정렬해서 출력하기

함수 포인터를 활용해서, flag로 여러 개의 함수를 하나의 함수로 제어하는 방법을 연구해봅시다.

학습(Study) & 목표(Objective) & 과제(Task)

주어지 문자열 배열을 사전식 오름차순으로 정렬하는 방법이나 글자 수가 가장 작은 단어 순으로 정렬하는 방법은 비교유형을 나타내는 Flag를 통해 작성할 수 있습니다. 그러나 이렇게 하면, 각각의 정렬함수를 매번 다시 작성해야 하는 단점이 있습니다.

각 쌍의 문자열을 비교하는 함수에 대한 포인터를 받아들이는 정렬함수를 작성하는 방법으로, 각각의 정렬함수를 호출하는 단점을 해결할 수 있습니다. 이렇게 하면 새로운 정렬 방법이 있을 때마다 정렬 함수에 대한 포인터만 받아오게 됩니다.

주어진 문자열 배열에서 비교함수에 따라 문자열을 정렬하는 string_sort() 함수를 구현해야 합니다.

void string_sort(const char **arr,const int cnt, int (*cmp_func)(const char* a, const char* b)){

}

이 함수에 전달된 인수는 다음과 같습니다.

문자열 배열 : arr

문자열 배열의 글자 수 : count

문자열 비교 함수에 대한 포인터 : cmp_func 

또한 다음 4가지 문자열 비교 함수를 구현해야 합니다.

1. int lexicographic_sort(char *, char *) : 사전 순으로 오름차순 정렬 함수(a, b, c)

2. int lexicographic_sort_reverse(char *, char*) : 사전 순으로 내림차순 정렬 함수(c, b, a)

3. int sort_by_number_of_distinct_characters(char *, chr*) : 고유한 문자 수를 기준으로 오름차순 정렬(aaa, abb, abc), 고유한 문자수가 같으면, 사전 순으로 오름차순 정렬 함수

4. int sort_by_length(char *, char*) : 글자수 기준으로 오름차순 정렬 함수, 글자수가 같으면 사전 순으로 오름차순 정렬 함수(cc, dd, aaa, bbb)

입력 형식(Input Format)

문자열 정렬 함수 string_sort()를 구현하고, 4개의 문자열 비교 정렬 함수를 구현합니다.

제약 조건(Constraints)

- 1<= 한 단어의 문자열 길이 <= 50

- 1 <= 모든 문자열의 총 길이 <= 2500

- 정렬 함수를 직접 구현해야하고, qsort 함수를 사용하지 않는다.

- 문자열은 영문 소문자로만 구성된다.

출력 형식(Output Format)

제공된 코드 조각은 코드의 논리를 점검한다. 출력은 문제에서 언급한 순서에 따라 4개의 비교 함수에 따라 정렬된 문자열을 표출한다.

입력 예제(Sample Input)

4

wkue

qoi

sbv

fekls

출력 예제(Sample Output)

fekls

qoi

sbv

wkue

wkue

sbv

qoi

fekls

qoi

sbv

wkue

fekls

qoi

sbv

wkue

fekls

주어진 코드

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int lexicographic_sort(const char* a, const char* b) {
 
}
 
int lexicographic_sort_reverse(const char* a, const char* b) {
 
}
 
int sort_by_number_of_distinct_characters(const char* a, const char* b) {
    
}
 
int sort_by_length(const char* a, const char* b) {
 
}
 
void string_sort(char** arr,const int len,int (*cmp_func)(const char* a, const char* b)){
 
}
 
 
int main() 
{
    int n;
    scanf("%d", &n);
  
    char** arr;
    arr = (char**)malloc(n * sizeof(char*));
  
    for(int i = 0; i < n; i++){
        *(arr + i) = malloc(1024 * sizeof(char));
        scanf("%s", *(arr + i));
        *(arr + i) = realloc(*(arr + i), strlen(*(arr + i)) + 1);
    }
  
    string_sort(arr, n, lexicographic_sort);
    for(int i = 0; i < n; i++)
        printf("%s\n", arr[i]);
    printf("\n");
 
    string_sort(arr, n, lexicographic_sort_reverse);
    for(int i = 0; i < n; i++)
        printf("%s\n", arr[i]); 
    printf("\n");
 
    string_sort(arr, n, sort_by_length);
    for(int i = 0; i < n; i++)
        printf("%s\n", arr[i]);    
    printf("\n");
 
    string_sort(arr, n, sort_by_number_of_distinct_characters);
    for(int i = 0; i < n; i++)
        printf("%s\n", arr[i]); 
    printf("\n");
}

답안 코드

정렬 알고리즘을 사용해서 string_sort()의 문자열을 정렬할 수 있습니다. 여기서는 Bubble sort를 사용하면, 아주 빠르게 문제를 해결할 수 있습니다.

비교함수의 몸체를 확인해보겠습니다.

사전 정렬을 구현하기 위해 string.h 라이브러리의 strcmp함수를 사용했습니다.

strcmp() 함수는 문자열을 비교하는 함수로, 같으면 0, 먼저 제시된 문자열이 더 큰 알파벳으로 시작하면 0보다 큰 수, 먼저 제시된 문자열이 더 작은 문자열로 시작하면 0보다 작은 수가 반환됩니다. (일반적으로 0, 1, -1) 같은 문자열로 시작하면, 2번째 문자를 비교하기 때문에, 사전적인 순서를 확인할 수 있습니다.

같은 문구는 순서를 바꿔도 같고, 안 바꿔도 같기 때문에 크게 의미는 없습니다. 이렇게 lexicographic_sort와 lexicographic_sort_reverse 함수를 구현할 수 있습니다.

3번째로 고유 문자 수를 토대로 정렬하는 함수입니다.

26개의 문자가 나타났는지를 저장할 배열 변수를 만들어서 알파벳이 나타났는지 확인하는 방법입니다.

크기가 26인 배열을 선언하고, 0으로 초기화합니다. 문자가 나왔으면, 1로 세팅하고, 1로 세팅한 수가 많은 문자를 반환하는 방법을 사용하였습니다.

길이별로 정렬하기 위해서는 string.h 라이브러리의 strlen() 함수를 사용하여 문자열의 정확한 길이를 구해서 비교하면 됩니다.

int lexicographic_sort(const char* a, const char* b){
    return strcmp(a, b) > 0;
}
 
int lexicographic_sort_reverse(const char* a, const char* b){
    return strcmp(a, b) <= 0;
}
 
int sort_by_number_of_distinct_characters(const char* a, const char* b){
    int c1 = 0, c2 = 0;
    int hsh1[26] = {0}, hsh2[26] = {0};
    int n1 = strlen(a);
    int n2 = strlen(b);
 
    for(int i = 0; i < n1; i++){
        hsh1[a[i] - 'a'] = 1;   
    }
 
    for(int i = 0; i < n2; i++){
        hsh2[b[i] - 'a'] = 1;   
    }
 
    for(int i = 0; i < 26; i++){
        if(hsh1[i])
            c1++;
        if(hsh2[i])
            c2++;
    }
    if( c1 != c2)
        return c1 > c2;
    else
        return strcmp(a, b)  > 0;
 
}
 
int sort_by_length(const char* a, const char* b){
    if(strlen(a) != strlen(b))
        return strlen(a) > strlen(b);
    else
        return strcmp(a, b) >  0;
}
 
void string_sort(char** arr,const int len,int (*cmp_func)(const char* a, const char* b)){
    for(int i = 1; i < len; i++){
        int j = i;
        char* p = arr[i];
        while(j > 0){
            if((*cmp_func)(arr[j-1],p) > 0 )
                arr[j] = arr[j-1];
            else
                break;
            j--;
        }
        arr[j] = p;
    }
}

추가 답안 코드

반환형식과 고유한 문자를 구하는 방법을 조금 수정하였습니다.

앞의 문자열이 먼저 나와야 하면 0보다 크고, 뒤에 나와야 하면 0보다 작고, 같으면 0으로 구현하였습니다. 이렇게하면, 사실상 lexicographic_sort() 와 _reverse() 함수는 없어도 기능 구현이 가능합니다.

하지만, 가독성이나 관리면에서는 있는 게 그래도 좋을 것 같습니다.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int lexicographic_sort(const char* a, const char* b)
{
    return strcmp(a, b);
}
 
int lexicographic_sort_reverse(const char* a, const char* b)
{
    return strcmp(b, a);
}
 
 
int sort_by_number_of_distinct_characters(const char* a, const char* b)
{
    int  c1  =  0 ,  c2  =  0 ; 
    int  hsh1 [ 26 ]  =  { 0 },  hsh2 [ 26 ]  =  { 0 }; 
    int  n1  =  strlen ( a ); 
    int  n2  =  strlen ( b );
    for ( int  i  =  0 ;  i  <  n1 ;  i ++ ) { 
        hsh1 [ a [ i ]  -  'a' ]  =  1 ;    
    }
    for ( int  i  =  0 ;  i  <  n2 ;  i ++ ) { 
        hsh2 [ b [ i ]  -  'a' ]  =  1 ;    
    }
    for ( int  i  =  0 ;  i  <  26 ;  i ++ ) { 
        if ( hsh1 [ i ]) 
            c1 ++ ; 
        if ( hsh2 [ i ]) 
            c2 ++ ; 
    }
    
    return (c1 != c2) ? c1 > c2 : lexicographic_sort(a, b);
}
 
int sort_by_length(const char* a, const char* b)
{
    int res = strlen(a) - strlen(b);
    return (res) ? res : lexicographic_sort(a, b);
}
 
void string_sort(char** arr,const int len,int (*cmp_func)(const char* a, const char* b))
{
    int half = len / 2;
    int sorted = 0;
    while(!sorted)
    {
        sorted = 1;
        for(int i = 0; i < len - 1; i++)
        {
            if(cmp_func(arr[i], arr[i+1]) > 0)
            {
                char *tmp = arr[i];
                arr[i] = arr[i+1];
                arr[i+1] = tmp;
                sorted = 0;
            } // end if
        } // end for
    } // end while
}
 
 
int main() 
{
    int n;
    scanf("%d", &n);
  
    char** arr;
    arr = (char**)malloc(n * sizeof(char*));
  
    for(int i = 0; i < n; i++){
        *(arr + i) = malloc(1024 * sizeof(char));
        scanf("%s", *(arr + i));
        *(arr + i) = realloc(*(arr + i), strlen(*(arr + i)) + 1);
    }
  
    string_sort(arr, n, lexicographic_sort);
    for(int i = 0; i < n; i++)
        printf("%s\n", arr[i]);
    printf("\n");
 
    string_sort(arr, n, lexicographic_sort_reverse);
    for(int i = 0; i < n; i++)
        printf("%s\n", arr[i]); 
    printf("\n");
 
    string_sort(arr, n, sort_by_length);
    for(int i = 0; i < n; i++)
        printf("%s\n", arr[i]);    
    printf("\n");
 
    string_sort(arr, n, sort_by_number_of_distinct_characters);
    for(int i = 0; i < n; i++)
        printf("%s\n", arr[i]); 
    printf("\n");
}