특정 문자를 제거하는 함수를 구현하라.

문자열에서 문자를 삭제하는 효율적인 함수를 작성하라. 함수 원형은 다음과 같다.
string removeChars( string str, string remove );
remove라고 인자로 전달된 문자열에 있는 모든 문자를 str이라는 문자열에서 삭제한다. 예를 들어, str이 "Battle of the Vowels: Hawaii vs. Grozny"로 주어지고 remove가 "aeiou"로 주어진다면 이 함수에서 str을 "Bttl f th Vwls: Hw vs. Grzny"로 변환시켜야 한다. 자신이 설계한 방식에 대해 합당한 근거를 제시하고 풀이의 효율에 대해 논하라.

작성자 : 김문규
최초 작성일 : 2008. 3. 30

풀이)

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

int is_remover(char ch, char* str);
char* remove_chars(char **str, char *remove);

int main(int argc, char** argv)
{
    char* org_str = NULL;
    char* remove = NULL;
    if(argc != 3) {
        printf("Usage : program [original_string] [remove_char]\n");fflush(stdout);
        return 0;
    } else {
        org_str = (char*)malloc(strlen(argv[1]));
        remove = (char*)malloc(strlen(argv[2]));
        sprintf(org_str, "%s", argv[1]);
        sprintf(remove, "%s", argv[2]);

        printf("original : %s, remover : %s\n", org_str, remove);fflush(stdout);
        printf("result : %s\n", remove_chars(&org_str, remove));

        free(org_str);
        free(remove);
    }
    return 1;
}

char* remove_chars(char **str, char *remove)
{
    int i = 0;

    int len = (!*str)?0:strlen(*str);
    char* pread = *str;
    char* pwrite = *str;

    for(i = 0; i < len; i++)
    {
        if(!is_remover(*pread, remove))
        {
            memcpy(pwrite, pread, 1);
            pwrite++;
        }
        pread++;
    }
    *(pwrite++) = '\0';

    return *str;
}

int is_remover(char ch, char* str)
{
    int i = 0;
    int len = (!str)?0:strlen(str);

    for(i = 0; i < len; i++)
    {
        if( ch == *str ) return 1;
        str++;
    }
    return 0;
}

<2> 모범 풀이 및 설명
 위의 풀이는 알고리즘의 효율 측면에서 문제가 있다. 현재의 풀이는 O(n*m)의 알고리즘이다(n:str 길이, m:remove 길이). 이 풀이는 Hash를 이용해서 O(n+m)의 알고리즘으로 구현가능하다.
 이와 같이 문자 검색의 경우에는 Hash를 이용하는 방법과 배열을 이용하는 방법 두가지가 있다. 비교되는 문자의 길이가 길고 사용 가능한 문자의 개수가 적을 경우에는 배열이 유리하고 반대의 경우에는 Hash가 유리하다. 역시나 그때 그때 경우에 따른 적절한 알고리즘의 선택이 중요하다.
 다음은 배열을 이용하여 알고리즘을 약간 개선한 풀이이다.

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

int is_remover(char ch, char* str);
char* remove_chars(char **str, char *remove);

int main(int argc, char** argv)
{
    char* org_str = NULL;
    char* remove = NULL;
    if(argc != 3) {
        printf("Usage : program [original_string] [remove_char]\n");fflush(stdout);
        return 0;
    } else {
        org_str = (char*)malloc(strlen(argv[1]));
        remove = (char*)malloc(strlen(argv[2]));
        sprintf(org_str, "%s", argv[1]);
        sprintf(remove, "%s", argv[2]);

        printf("original : %s, remover : %s\n", org_str, remove);fflush(stdout);
        printf("result : %s\n", remove_chars(&org_str, remove));

        free(org_str);
        free(remove);
    }
    return 1;
}

int check[128]; // assume char is ASCII only.
char* remove_chars(char **str, char *remove)
{
    int i = 0;

    int len = (!*str)?0:strlen(*str);
    char* pread = *str;
    char* pwrite = *str;

    char* ptemp = remove;
    int len2 = (!remove)?0:strlen(remove);
    for(i=0; i < len2; i++)
    {
        check[*ptemp++] = 1;
    }

    for(i = 0; i < len; i++)
    {
        if(!check[*pread])
        {
            memcpy(pwrite, pread, 1);
            pwrite++;
        }
        pread++;
    }
    *(pwrite++) = '\0';

    return *str;
}