indexOf vs for, 왜 indexOf로 해결되는거지?

이건, 좀 의아한 기록이고 왜 그런지 모르겠어서 남기는 메모인데...

 

요즘 해커랭크에서 문제를 풀어보는 편인데,

가볍게 풀려고 Easy 난이도의 Two Strings 라는 문제를 봤다.

 

설명하자면,

그냥 문자열 2개 비교해서, 서로 동일한 문자가 있으면 'YES', 없으면 'NO'를 리턴하는건데

내가 어떤 부분에서 이해가 되질 않아서 이렇게 포스팅까지 하냐면...

 

처음에 아래와 같이 쉽게 for문 2개 코드로 작성 제출했는데

function twoStrings(s1, s2) {
    // Write your code here

    for(let i = 0, length = s1.length; i < length; i++){
        for(let j = 0, jlength = s2.length; j < jlength; j++){
            if(s2[j] === s1[i]){
                return 'YES';
            }   
        }
    }
    
    return 'NO';
}

3개 테스트 케이스에서 Time limit exceeded가 발생을 했다.

 

그렇게 한참을 고민.

고민.

고민.

고민.

고민.

Easy 난이도인데, 이게 이렇게 고민거린가...?

고민.

고민.

또 고민.

 

그러다 혹시나 싶은 마음에 아래와 같이 작성했는데

function twoStrings(s1, s2) {
    // Write your code here
    
    for(let i = 0, length = s1.length; i < length; i++){
        if(s2.indexOf(s1[i]) > -1){
            return 'YES';
        }   
    }
     
    return 'NO';
}

통과했다.

 

...????

 

그냥 내부 for문을 indexOf로 바꾼건데, 통과를 해버렸다.

 

이게 왜, 의문거리냐면...

사실 내 생각으론 둘의 시간복잡도는 O(n^2)로 같기 때문이다.

for문은 애초에 주어진 데이터를 전체 반복하니까...

이중 포문이면 n^2 인거고.

indexOf도 시간복잡도는 O(n)인데, 그게 for문안에 있으니까 O(n^2)인거고...

 

심지어 혹시 indexOf가 Javascript 내부적으로 무언가 내가 알지 못 하는 신박한 방법을 통해서

for 보다 빠른 프로세스를 가지는 건가, 싶어서 찾아봤는데

How to find an item in a JavaScript array (+performance tests) (nikitahl.com)

How to find an item in a JavaScript array (+performance tests)

...for문이 더 빠르다는거다.

(물론 저건 String이 아니라 Array지만, 동작매커니즘 자체는 동일할테니까)

 

왜 때문에 그런거에요...대체...?

사실 포스팅을 하는 지금도 왜 때문인지 모르겠다...

이미 있는 함수를 굳이 만드려고하지말고 잘 쓰는 게 좋다,

라는 교훈을 얻고 마침표를 찍어야하나 싶다가...

결국 ECMA 원문까지 열어봤는데도 모르겠다.

ECMA-262_1st_edition_june_1997.pdf (ecma-international.org)

 

1. Call ToString, giving it the this value as its argument.
2. Call ToString(searchString).
3. Call ToInteger(position). (If position is undefined or not supplied, this step produces the value 0).
4. Compute the number of characters in Result(1).
5. Compute min(max(Result(3), 0), Result(4)).
6. Compute the number of characters in the string that is Result(2).
7. Compute the smallest possible integer k not smaller than Result(5) such that k+Result(6) is not greater than Result(4), and for all nonnegative integers j less than Result(6), the character at position k+j of Result(1) is the same as the character at position j of Result(2); but if there is no such integer k, then compute the value -1. 8. Return Result(7)

내 짧은 영어로 해석해보자면,

예를들어, str.indexOf(keyword) 라고 한다면

1. 찾아볼 전체 문자열(str)을 가져오고
2. 찾으려는 키워드(keyword)를 가져오고
3. 찾으려는 시작점 Index를 가져오는데, 없으면 0으로 세팅되고
4. 전체 문자열의 길이를 계산하고
5. (0이랑 찾으려는 시작점 중 큰 값)을 추출해내고, 그걸 또 전체 문자열과 비교해서 작은 수를 계산해내고
6. 찾으려는 키워드(keyword)의 길이를 계산하고
7. 이제 상수 k를 통해서 결국 위에서 계산된 시작점에서부터 동일한 거 있는지 str을 뒤져보고 있으면 해당 index를 리턴, 없으면 -1을 리턴

이건데...

생짜 for문으로 하면 5번과정이 없어서 그런가, 싶다가도.

사실 결국 둘 다 0번 인덱스부터 반복문이 시작되는거면 다를 게 없는데

(오히려 min,max 절차가 더해지니 함수호출로 복잡도가 올라가는 거 아닌가?)

 

...

 

그래서 이 포스팅의 결론은...

 

몇백줄 짜리 코드를 짜다가 발생한 버그로 골머리를 앓는 학생의 뒤를,

산보하듯 스윽, 걸어가다가 곁눈질만으로

"N번째 줄에 버그가 있네, 학생." 이라는 명언을 남겨주셨던...

내게 SW공학을 가르쳐 주셨던 강쌤의 명언을 떠올리며 포스팅을 마무리 짓는다.

 

굳이 있는 기능을 만드는 건 바보들이나 하는 짓입니다.

 

그러니, 이미 있는 indexOf를 잘 쓰도록 하자.

(사실 더 파고들고 싶긴한데...회사 점심시간이 끝나간다...)