[Leetcode] 14. Longest Common Prefix (C)

되게 오랜만에 포스팅을 적는것 같다. 회사들어가기 전에는 회사 생활 하면서도 이걸 잘 유지할 수 있을줄 알았는데 여러모로 어려운 일이었다는걸 알게되었다..😭

하여간 요즘 C를 다시 연습하고 있기때문에 Leetcode에 쉬운 문제들을 C로 풀어보고 있다.

이번에 푼 문제는 14. Longest Common Prefix라는 문제였다.

입력으로 strsSize개의 문자열이 들어올때 해당 문자열들의 가장 긴 prefix를 찾는 문제였다.

첫 번째 구현 : Two pointer?

나는 기존의 Longest Common Prefix와 문자열을 순서대로 비교하며 공통된 prefix를 갱신하는 방법을 택했다. 예를 들어 input으로 strs=[“flower”,”flow”,”flight”] 세 개의 문자열이 들어왔을때를 가정해보자.

먼저 common이라는 Longest common prefix값을 저장할 문자열을 하나 만들고, 해당 문자열은 input의 첫번쨰 문자열로 초기화 한다.

따라서 초기 상태의 common은 “flower”, 즉 str[0]의 주소값을 가리키고 있을거다.

이후 이 common을 다음 문자열인 flow와 한글자씩 비교한다.

이 경우 “flow” 4글자가 같으므로 common을 “flow”로 갱신한다.

다음으로 다음 문자열인 “flight”와 common을 비교한다.

이경우 “fl”까지 같으므로 결과는 “fl”이 된다.

구상했을때는 정말 간단해보이는 알고리즘이었는데 C로 구현하려고 하니까 너무 힘들었다..

char* longestCommonPrefix(char** strs, int strsSize) {
    char* common = strs[0];

    int common_last = strlen(common);

    for(int i = 1; i<strsSize; i++)
    {
        char* compare = strs[i];

        int common_current =0;
        int compare_current =0;

        while(common_current<common_last && compare_current <common_last)
        {
            if(common[common_current]==compare[compare_current])
            {
                common_current++;
                compare_current++;
            }else{
                if(common_last>common_current)
                    common_last = common_current;
                break;
            }

        }  
    }
    char* res = (char *)malloc(sizeof(char) * (common_last+1));
    strncpy(res,common,common_last);
    res[common_last]='\0';
    return res;
}

결과는 아래와 같다.

c가 빠르긴 빠르다.

시간 복잡도는 O(n*m)이었는데 개선할 방법이 있을것 같기도 하고.

Memory가 의외로 더 줄일 수 있었나보다.

두 번쨰 시도 : 개선

답지를 보니까 알고리즘은 대충 일반적인 방법이었던것 같다.

헉, 근데 답안 코드를 보니까 내가 놓친 부분도 있고, 미처 이렇게 까지 생각하지 못했던 부분이 있다.

1. strstr함수사용
2. 입력 문자열 배열을 활용해 리턴값 반환
3. (minor) 입력 검증

strstr(st1,st2)

#include <string.h>
char *strstr(const char *string1, const char *string2);

• string1에서 string2의 첫번째 일치하는 문자열을 찾는다.
• 일치하는 문자열이 있다면 해당 위치의 포인터를 반환한다.
• 그렇지 않다면 NULL을 반환한다.

+) 갑자기 궁금해져서 string2자리에 ““을 넣어서 시도해보았다.

int main() {
    char* a = "hello";
    char* b = "";
    printf("%c",*strstr(a,b)+1); //output : h
}

흠.. 의외로 a의 첫번째 주소값이 반환되었다.

궁금해서 왜그런가 하고 봤는데 내부적으로 b가 공백 문자면 바로 string1을 반환하게 되어있다. (stackoverflow)

하여간 이걸로 다시 코드를 작성해보면 다음과 같다.

char* longestCommonPrefix(char** strs, int strsSize) {
    if(strsSize==0){
        return 0;
    }
    char* common = strs[0];
    for(int i =0; i<strsSize; i++){
        while(*common){
            if(strstr(strs[i],common)!=strs[i]){
                common[strlen(common)-1]='\0';
            }else{
                break;
            }
        }
        
    }
    return common;
}

촴..ㅋㅋㅋ 메모리가 더 늘어버렸다..

원래 내 코드랑 적절히 섞어서 원래 내 코드베이스로 개선을 하는게 성능 측면에서 더 나을것 같아서 세번째 시도를 했다.

세번째 시도 : 처음 코드 최적화

char* longestCommonPrefix(char** strs, int strsSize) {
    char* common = strs[0];

    int common_last = strlen(common);

    for(int i = 1; i<strsSize; i++)
    {
        char* compare = strs[i];

        int common_current =0;
        int compare_current =0;

        while(common_current<common_last && compare_current <common_last)
        {
            if(common[common_current]==compare[compare_current])
            {
                common_current++;
                compare_current++;
            }else{
                if(common_last>common_current)
                    common_last = common_current;
                break;
            }

        }  
    }
    common[common_last] = '\0';
    return common;
}

마지막에 res를 동적할당하는 부분만 변경했다.

근데 결과가 두번째 시도와 비슷하게 나왔다. 아마 동적할당은 크게 영향을 미치는 부분이 아니었나보다.

메모리 사용량을 얘네가 어떻게 계산을 하는지 잘 모르겠는데 나중에 시간나면 한번 찾아봐도 좋을것 같긴하다.

결론

결론은 두번째가 가장 나은 코드같다. 첫번째보다 메모리 사용량이 늘긴했지만 가독성과 코드 수가 훨씬 줄었다.

오늘 배운건 아래와 같다.

• leetcode에서 결과반환시 input배열을 활용할수도 있다 (근데 왠지모르게 이번엔 메모리 사용량이 늘었다.🤔🤔🤔)
• strstr로 문자열에 포함된 문자열을 탐색할 수 있다.
• 문자열 끝부분을 drop하고 싶을때는 strncpy말고도 그냥 끝내고 싶은 부분에 ‘\0’을 넣는것도 방법이다.(나중에 두 방법에 대해서는 비교를 좀 해봐야겠다.)