[JS 알고리즘 문제] #4 getIndexOf
[문제]
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;
}
}
}
}
str = '123456789', char = '9' 인 경우
str.includes(char) 는 true 이지만 이를 알아내기 위해서 9 번의 연산이 필요합니다.
그리고 0 에서 다시 str.length 까지 9 번의 연산을 수행해야 return i
Worst Case 는 str 의 길이를 N 으로 했을 때, 시간 복잡도는 N + N 이 됩니다.
참고로 str.includes(char) 는 불필요합니다.
시간 복잡도를 전혀 고려안하고, 기본적인 알고리즘 문제를 풀기위해 하다보니 저런방식으로 풀게 되었습니다! str.includes(char)가 불필요하다면, 혹시 시간 복잡도를 고려한 좀 더 좋은 알고리즘이 어떤게 있을까요?