[Leetcode][C++][난이도 Medium] Find the Index of the First Occurrence in a String ((구) Implement strStr)

난이도 Medium의 릿코드 문제 Find the Index of the First Occurrence in a String에 대한 설명 및 C++ 풀이에 대해 살펴보겠습니다. 이 문제는 과거에 Implement strStr 이라는 easy 난이도 문제였습니다. 

 

[사진 1] Implement strStr  (난이도 easy) 때의 문제

 

이 당시의 문제는 소스 string인 haystack에서 탐색하려는 string인 needle이 있으면 해당 인덱스를 반환하고, 아니면 -1을 반환했었습니다. 지금 변경된 문제에서는 needle이 empty string일 때, 0을 반환하는 조건이 추가되었습니다. 변경된 문제에 대한 정보는 아래 글에서 확인 가능하며, 이와 비슷한 코딩 테스트 문제들도 인터넷에서 바로 확인할 수 있습니다. 

 

Find the Index of the First Occurrence in a String 문제 관련 C++ 함수

 

참고 사항으로, 문제에서 제시하는 strStr과 약간 다르지만, C++에도 strstr 함수가 있습니다. C++의 strstr 함수는 아래의 함수 원형과 같이, str1에서 str2와 일치하는 문자열이 있는지를 탐색하는 함수입니다. 만약 str2와 일치하는 문자열을 str1에서 발견하면, str1의 해당 위치의 char 포인터 타입을 반환합니다. 

 

char* strstr(char* str1, const char* str2)

 

strstr 함수 이외에 C++에는 문자열 처리를 위한 다양한 내장 함수들을 제공하고 있습니다. 인터넷에서 참고 사항으로 확인해보는 것을 추천합니다.

 

 

Find the Index of the First Occurrence in a String 문제 분석

 

[사진 2] Find the Index of the First Occurrence in a String 문제

 

기존 문제와 달라진 점은 needle이 empty string인지 아닌지의 여부와 관계없이, haystack에 needle에 해당하는 string이 없으면 -1, 아니면 해당하는 string이 등장하는 index를 반환하는 것으로 바뀌었습니다. 문제를 해결하기 위한 알고리즘은 전과 비슷합니다. 

 

첫번째 예제부터 살펴보겠습니다. haystack은 "sadbutsad" 이고, needle은 "sad"입니다. 여기서 "sad"라는 문자열이 haystack에서 index 0과 6에서 등장합니다. 처음 등장하는 index를 반환해야 하므로, 0이 반환됩니다. 두번째 예제는 haystack이 "leetcode", needle이 "leeto" 입니다. 그런데 "leeto"는 haystack에 존재하지 않습니다. 따라서 -1이 반환됩니다.

 

코딩 테스트를 위한 leetcode의 문제에 대한 추가 설명은 인터넷에서 추가로 확인할 수 있습니다.

 

 

Find the Index of the First Occurrence in a String 문제의 C++ 풀이

 

class Solution {
public:
    int strStr(string haystack, string needle) {
        if (needle.empty())
            return -1;
        
        int result = haystack.find(needle);

        if (result == string::npos)
            return -1;
        else
            return result;
    }
};

 

이제 제가 작성한 코드를 살펴보겠습니다. 저는 string의 built-in 함수를 사용해서 문제를 해결했습니다. 먼저 needle이 empty라면 -1을 반환합니다. 만약 아니라면 haystack에서 needle이 등장하는지, string의 built-in 함수인 find를 적용했습니다. find 함수를 사용하면 result에 needle이 처음 등장한 index가 저장됩니다. 만약 발견되지 않았다는 것을 확인하고 싶을 때는 string::npos로 조건문을 걸어주었습니다. 이 경우도 역시 -1을 반환합니다. 아니라면 result에 저장된 index를 반환했습니다.

 

제가 작성한 코드 이외의 다른 사람의 C++ 풀이도 leetcode 사이트에서 확인 가능합니다.

 

 

Find the Index of the First Occurrence in a String 문제의 다른 C++ 풀이

 

class Solution {
public:
    int strStr(string haystack, string needle) {
        int m = haystack.size(), n = needle.size();
        if (!n) {
            return 0;
        }
        vector<int> lps = kmpProcess(needle);
        for (int i = 0, j = 0; i < m;) {
            if (haystack[i] == needle[j]) { 
                i++, j++;
            }
            if (j == n) {
                return i - j;
            }
            if (i < m && haystack[i] != needle[j]) {
                j ? j = lps[j - 1] : i++;
            }
        }
        return -1;
    }
private:
    vector<int> kmpProcess(string needle) {
        int n = needle.size();
        vector<int> lps(n, 0);
        for (int i = 1, len = 0; i < n;) {
            if (needle[i] == needle[len]) {
                lps[i++] = ++len;
            } else if (len) {
                len = lps[len - 1];
            } else {
                lps[i++] = 0;
            }
        }
        return lps;
    }
};

 

이제 다른 사람이 작성한 코드를 살펴보겠습니다. 이 분은 brute force와 KMP 알고리즘 2개를 각각 적용해서 문제를 해결하셨네요. KMP는 Knuth-Morris-Pratt 알고리즘입니다. 시간복잡도가 O(N) 입니다. 여기서 N은 haystack의 길이입니다. Brute force로 문제를 단순하게 해결하고 싶을 때는 N의 제곱만큼 시간복잡도가 소요됩니다. KMP를 적용하면 N만큼만 시간복잡도가 소요되어, 대학교의 알고리즘 수업에서 문자열 탐색할 때 꼭 배우는 알고리즘입니다. KMP 알고리즘은 숙지해두면 좋은 사항이니, 구글에 KMP 알고리즘만 검색하셔도 예제와 함께 공부하실 수 있으십니다.

 

 

지금까지 릿코드의 난이도 Medium 문제인 "Find the Index of the First Occurrence in a String"에 대해서 살펴보았습니다. 아마 이 문제가 Medium인 이유는 built-in 함수를 사용하지 않고, KMP 알고리즘을 구현할 수 있는지를 묻는게 목표였지 않았나 싶은데요, 꼭 다른 풀이 방법들도 살펴보시기 바랍니다.