[JS 알고리즘 문제] #4 getIndexOf

[cheonmr]

[문제]
1개의 character와 string이 주어졌을 때, 그 string에서 그 character의 첫번째 위치(first index)를 리턴하는 프로그램을 작성하라. 

string이 주어진 character를 2개 이상 포함하고 있다면, 첫번째 character의 위치(index)를 리턴하라. 

character가 string에 포함되어 있지 않으면, ‘-1’를 리턴하라. 

indexOf 함수를 사용하지 않는다. 

function getIndexOf(char, str) {

    // your code

}

[예제] 

var output = getIndexOf('a', 'I am a hacker'); 

console.log(output); // 2 

[알고리즘] 

• char이 str에 포함이 되어있는지 확인하고, 안되어있으면 ‘-1’를 리턴한다.
• 포함되어있다면, for 문을 돌려, str의 각 문자가 주어진 char와 같은지 확인하고, 같으면 index를 리턴한다.

[Solution] 

function getIndexOf(char, str) {
 if(!str.includes(char)) {
     return -1;
    } else {
         for(var i = 0; i < str.length; i++) {
             if(str[i] === char) {
                 return i;
        }
      }
    }
  }

Comments

[kdj]

str = '123456789', char = '9' 인 경우
str.includes(char) 는 true 이지만 이를 알아내기 위해서 9 번의 연산이 필요합니다.
그리고 0 에서 다시 str.length 까지 9 번의 연산을 수행해야 return i
Worst Case 는 str 의 길이를 N 으로 했을 때, 시간 복잡도는 N + N 이 됩니다.
참고로 str.includes(char) 는 불필요합니다.

[cheonmr]

시간 복잡도를 전혀 고려안하고, 기본적인 알고리즘 문제를 풀기위해 하다보니 저런방식으로 풀게 되었습니다! str.includes(char)가 불필요하다면, 혹시 시간 복잡도를 고려한 좀 더 좋은 알고리즘이 어떤게 있을까요?