[35일차] Multiple Pointers - isSubsequence 리뷰

Multiple Pointers - isSubsequence

https://velog.io/@eprnfmfmfm/28일차

서론

이 문제에서는 O(N + M)의 시간 복잡도의 알고리즘 혹은 O(1)의 공간복잡도의 알고리즘을 구현해내도록 요구하고 있다. 나는 여기서 둘 다를 충족시키고 싶어 따로 배열을 사용하지 않고 string의 특성만으로 구현해 냈다.

본론

다중포인터를 이용해서 인자로 받는 첫번째 문자열과 두번째 문자열에 각각 포인터를 두었고, 일치하지않으면 일치할때까지 두번째 문자열을 왼쪽에서 오른쪽으로 이동시키며 비교했다.마지막으로 첫번째 포인터의 값을 첫번째 문자열의 길이와 비교해서 같으면 true를 반환하고, 같지 않으면 false를 반환했다.

강의에서 제시한 해결책과 나의 해결책은 근본적으로 원리는 같았으나, 강의에서 제시한 해결책이 훨씬 간결하고 깔끔하게 작성되었음으로 여기에 소개하고자 한다.

 for(let i = 0; second < str2.length; i++){
        //문자가 같으면 str1의 포인터를 이동
        if(str1[first] === str2[second]){
            first++;
        }else{
            //같지 않으면 str의 포인터를 이동
            second++;
        }
    }

    //str1의 포인터가 모두 이동했는지 확인.
    if(first === str1.length){
        return true;
    }else{
        return false;
    }

나는 이렇게 for루프 밖에 if를 두어 true, false를 비교했으나,

  while (j < str2.length) {
    if (str2[j] === str1[i]) i++;
    if (i === str1.length) return true;
    j++;
  }

강의의 솔루션에서는 이렇게 루프안에서 비교를 하는 것으로 O(N+M)의 시간복잡도를 구현해냈다. 나는 엄밀히 말하면 O(N+M)을 구현한 것은 아니었다.

또, 강의의 솔루션에서는 재귀를 사용하여 O(1)의 시간복잡도가 아닌 알고리즘을 소개하였다. 다음 강의파트가 재귀이니 이 솔루션은 재귀파트를 모두 들은 뒤에 다시 이 문제를 재귀를 이용해 풀어보면서 소개하려고 한다.

참고

https://www.udemy.com/share/105zfq3@ZLDm9Qh9arnE90sWYrAnWl5LunsyQpZLPrvFRMkYFWiFxf9Zd5A6VNjq61F7uo-SPQ==/