[알고리즘 - LeetCode] Implement strStr()

문제

Implement strStr().

Return the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.

What should we return when needle is an empty string? This is a great question to ask during an interview.

For the purpose of this problem, we will return 0 when needle is an empty string. This is consistent to C's strstr() and Java's indexOf().

strStr 함수는 문자열로 된 hayStack, needle 이라는 2개의 인자를 가진다.
needle과 일치되는 문자열이 hayStack에 있을 경우 일치되는 문자열이 시작되는 index를 반환하고, 그렇지 않은 경우에는 -1을 반환한다. needle이 빈 문자열일 경우 0을 반환한다.

Example 1:

Input: haystack = "hello", needle = "ll"
Output: 2

Example 2:

Input: haystack = "aaaaa", needle = "bba"
Output: -1
Clarification:

---

풀이

매우 오랜만의 리트코드라 easy로...

인덱스 관련 메소드 대부분이 값이 존재할 경우 해당 index를 존재하지 않을 경우 -1을 반환한다는 것과, 얼마 전 frontendmasters 수업에서 뜬금없이 감명받은 (ㅋㅋㅋㅋ) substring 메소드를 조합하여 풀었다.

일단 haystack이 비어있는 예외의 경우는 early return으로 처리하고 시작한다.
어쩐지 요즘엔 !needle.length 보다는 명확하게 needle.length === 0을 사용하는 편이다.

그리고 나서는
1. haystack string을 순회하며
2. 순회 중인 인덱스부터 needle의 문자열 수만큼의 인덱스를 잘라서 needle과 동일한지 비교를 한다.

제출 코드

for loop

const strStr = function(haystack, needle) {
    if (needle.length === 0) {
        return 0;
    }
    
    for (let i = 0; i < haystack.length; i++) {
        const check = haystack.substring(i, i + needle.length);
        if (check === needle) {
            return i;
        }
    }
  return -1;
};

순회의 시작은 for문 이쥬~~?

for loop을 forEach로 변경해도 되나요?

아니요

forEach

forEach()는 각 배열 요소에 대해 한 번씩 callback 함수를 실행합니다. map()과 reduce()와는 달리 undefined를 반환하기 때문에 메서드 체인의 중간에 사용할 수 없습니다. 예외를 던지지 않고는 forEach()를 중간에 멈출 수 없습니다. 중간에 멈춰야 한다면 forEach()가 적절한 방법이 아닐지도 모릅니다.
mdn 문서 중

const strStr = function(haystack, needle) {
    if (needle.length === 0) {
        return 0;
    }
    
// forEach 문은 멈추지 않음
    [...haystack].forEach(_, index => {
        const check = haystack.substring(index, index + needle.length);

        if (check === needle) {
                return index;
            }
    });
    return -1;
};

forEach문은 멈추지 않고 배열을 모두 순회하며, undefiend를 반환하는 메소드이므로 단순히 for loop을 대체하는 메소드로 사용하는 것은 옳지 않다. 따라서 위의 코드도 당연히 작동하지 않는다.

 

findIndex

findIndex() 메서드는 주어진 판별 함수를 만족하는 배열의 첫 번째 요소에 대한 인덱스를 반환합니다. 만족하는 요소가 없으면 -1을 반환합니다.

const strStr = function(haystack, needle) {
    if (needle.length === 0) {
        return 0;
    }
  
  return [...haystack].findIndex((_, index) => haystack.substring(index, index + needle.length) === needle);
};

특별히 needle이 여러 번 존재할 수 있다는 엣지 케이스들이 없었으므로 findIndex을 사용했고, 배열 메소드이므로 es6 문법으로 문자열을 배열로 바꿨다.
ie 지원으로 es5를 사용하던 회사에 잠시 있었던 기억이 떠오름니다.. findIndex도 ie를 지원하지 않는군여..

그러나 사실은 그 무엇보다 가장 딱 맞는 메소드가 있었으니..

indexOf

const strStr = (haystack, needle) => haystack.indexOf(needle);

문자열 메소드로도 사용되는지 오늘 처음 알았다고한다.. 알고리즘 공부는 꾸준히..

타 제출 코드와 실행 속도 비교

제출했던 코드들 모두 실행속도는 나쁘지 않았다. for 문이던 다른 메소드를 사용하던 순회를 한번은 해야하므로 시간 복잡도는 최대 O(n)이 되는 것으로

근데 왜 for loop을 잘 쓰지 않나요?

얼마 전 회사에 들어온 과제 코드를 리뷰하면서 for loop을 쓴 것에 대한 이야기가 오갔다.
나 역시 번거로운 for loop 사용을 선호하지 않지만 잘 모르는 사람들이 for loop을 쓴다는 듯한 뉘앙스의 이야기가 오고가길래 특별한 이유가 있는 것인가?!! 하는 궁금증에 함께 있던 동료에게 물어보니
array의 여타 메소드들과 for loop은 달리 작성할 것들이 많아 실수할 범위가 넓다는 것이다. 두둥탁.

for ([초기문]; [조건문]; [증감문]) {...}
  
for (let i = 0; i < blahblah.length; i++) {...}

맞네.. 맞는 말이다.
소괄호 내부에 초기, 조건, 증감문에서 모두 오타나 실수를 할 여지가 많다.. 실제로 증감문에서 i++, i += 이 아닌 i + 1 이렇게 작성해두고 몇 십분을 삽질했던 기억도 있다.. 허허

메소드를 사용한다면, 아래와 같이

blahblah.forEach(blah => ...)
blahblah.map(blah => ...)

확실히 휴먼에러를 줄일 수 있다.

상황에 따라 최선의 방법을 선택하되 가독성이 높고 에러를 방지하는 방향을 지향하는 것이 좋은 것 같다. 갈 길이 멀군여..