알고리즘 문제 5

문제 설명

 

배열에 들어가있는 문자열들에서 공통으로 시작되는 단어를 추출하는 문제이다.

처음에 내가 구현하려는 방법은 배열에 0번 인덱스에 들어가있는 단어들을 for..of문으로 작성을한 후 그 단어들이

같은 인덱스 순서에 존재하는지 단어 하나하나 다 검사하는 로직으로 풀려고 했다.

 

for(let value of strs[0]) {
	for(let i=1, i<strs.length; i++) {
    .
    .
    }

 

대략적인 개요는 이런데 결국 잘안풀려서 다른 풀이를 찾아보았다.

 

const getPrefix = strs => {
 let prefix = strs[0];    
    if(strs.length === 0){	 
        prefix = "";
    }
    for(let i=1; i<strs.length; i++){            
        while(strs[i].indexOf(prefix) !== 0){               
            prefix = prefix.substring(0, prefix.length-1)
            console.log('prefix:' + prefix)
        }
    }
    return prefix; 
}

 

처음에 prefix변수에 strs배열의 첫번째 단어를 할당한다.  if문으로 strs가 빈 배열일때 빈 문자열을 반환해준다.

for(let i=1; i<strs.length; i++)은 strs배열을 1번 인덱스부터 끝까지 검사하겠다는거고 밑에 있는 while문이

검사하는 코드다.

while(strs[i].indexOf(prefix) !== 0)코드가 핵심인데 이 구문은 str배열의 i번째 요소에 prefix에 할당된 단어가 없으면

실행한다는거다. indexOf(element)메소드는 인자로 들어가 있는 값이 없다면 -1을 반환하고 요소랑 같은 공통으로 시작되는 

단어가 있다면 0을 반환한다. 그래서 만약 없다면 while문 안에 있는 코드가 실행되는데 prefix에 할당된 변수에서 뒤에 문자열 

하나를 잘라서 다시 할당해주는 코드이다. while문은 공통으로 시작하는 단어가 있을때까지 루프를 돈다.

 

예를 들어서 strs에  ['start', 'stair', 'step']이 할당되어 있다면 0번 인덱스  단어는 'start'다. 이단어는 prefix변수에 할당된다.

그리고 1번 인덱스 단어인 stair이랑 비교하는데 stair에는 start단어가 없기때문에 prefix변수에 'star'이 할당된다.

그리고 'stair'에는 'star'가 없기때문에 prefix변수에는 'sta'가 할당된다. 'stair'에는 'sta'로 시작하기때문에 while문을 

종료하고 다시 for문으로 들어가 2번 인덱스 'step'과 비교한다. 현재 prefix에는 'sta'가 할당 되어있어서 없기때문에

prefix에는 'st'가 할당된다. 'step'에는 'st'가 존재하기때문에 while문을 종료하고 for문도 종료하면 prefix에 할당된

'st'가 최종적으로 반환되는 로직이다.

단어 하나씩 검사하는건 맞았지만 공통된 단어를 줄여가면서 찾는 로직을 생각해내는게 상당히 어려웠다.