Find the Index of the First Occurrence in a String

---

💬 문제

[문제 링크]

문자열 haystack에 처음으로 등장하는
문자열 needle의 시작 인덱스를 반환 (strstr)
없으면 -1 반환

✍️ 나의 풀이

/**
 * @param {string} haystack
 * @param {string} needle
 * @return {number}
 */
var strStr = function(haystack, needle) {
    return haystack.indexOf(needle);
};

자바스크립트의 string 메소드인 indexOf를 사용하여 결과값 반환

📌 결과

Accepted
Runtime 59ms (Beats 20.91%)
Memory 48.83MB (Beats 50.91%)

📚 러닝 포인트

이미 자바스크립트에 구현되어 있는 함수라서 너무 간단히 풀어버렸다. 그래서 직접 구현해보는건 어떨까 싶어 예전에 42에서 C로 구현한 strstr을 생각하며 풀어보았다.

var strStr = function(haystack, needle) {
    for (let i = 0; i < haystack.length; i++) {
        let j = 0
        for (j; j < needle.length; j++) {
            if (haystack[i + j] !== needle[j])
                break ;
        }
        if (j === needle.length)
            return i;
    }
    return -1;
};

그러나 2중 for문이어서 그런지 효율은 좋지 않았고, 다른 방법을 찾아보던 중 for문 하나로도 풀 수 있다는 걸 알게 되었다.

var strStr = function(haystack, needle) {
    let j = 0;
    for (let i = 0; i < haystack.length; i++) {
        if (haystack[i] === needle[j]) {
            j++;
            if (j === needle.length)
                return i - j + 1;
        } else {
            i -= j;
            j = 0;
        }
    }
    return -1;
};

굳이 haystack 순회 인덱스인 i를 고정시켜두지 않고 needle 순회 인덱스인 j와 함께 증가시켜 나가다가 두 문자가 같지 않으면 i 에서 j를 빼서 다음 인덱스부터 다시 확인하는 것이다. 따라서 모두 같음을 알게된 순간 (j === needle.length) 현재 i에서 j만큼 증가했으므로 haystack에서 needle이 시작하는 위치는 i - j + 1이다. (한번 더 증가한 j를 뺐으므로 +1) 이 알고리즘으로 제출해봤더니 무려 44ms(91.92%) 48.25MB(93.67%)의 결과가 나온다!