___  ___    _ _    _  _ _____   _____
 / __|/ _ \  | | |  | || |_ _\ \ / / __|
| (_ | (_) | |_  _| | __ || | \ V /| _|
 \___|\___/    |_|  |_||_|___| \_/ |___|

 --- A GOPHER-LIKE INTERFACE FOR HIVE BLOCKCHAIN ---

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

BY: @cheonmr | CREATED: March 27, 2018, 1:18 a.m. | VOTES: 2 | PAYOUT: $0.11 | [ VOTE ]

[문제]
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;
       }
     }
   }
 }

TAGS: [ #kr-dev ] [ #kr ] [ #kr-newbie ] [ #developer ] [ #javascript ]

Replies

@kdj | March 27, 2018, 1:17 p.m. | Votes: 0 | [ VOTE ]

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 | March 28, 2018, 4:36 a.m. | Votes: 0 | [ VOTE ]

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

[ BACK TO TRENDING ] [ BACK TO MENU ]
CMD>