*문제
strs은 단어가 담긴 배열입니다.
공통된 시작 단어(prefix)를 반환해주세요.
예를 들어
strs = ['start', 'stair', 'step']
return은 'st'
strs = ['start', 'wework', 'today']
return은 ''
오늘 문제는 많이 복잡하다
차근차근 알아보자
const checkPrefix = (size, strs) => {
let compareString = strs[0].slice(0, size);
for(let i = 1; i < strs.length; i++) {
if(!strs[i].startsWith(compareString)) return false;
}
return true;
}
const getPrefix = strs => {
if(strs.length === 0) return '';
let minlength = 234234234;
for(let i = 0; i < strs.length; i++) {
if(strs[i].length < minlength) minlength = strs[i].length;
}
let s = 1, e = minlength, mid;
let anslength = 0;
while(s <= e) {
mid = Math.floor((s + e)/2);
if(checkPrefix(mid, strs)) {
s = mid + 1;
anslength = anslength < mid ? mid : anslength;
} else e = mid - 1;
}
const answer = strs[0].slice(0, anslength);
return answer;
}
getPrefix(['start', 'stair', 'step']);먼저 checkPrefix 함수를 만들어서 size와 strs 단어가 담긴 배열을 인자로 받는다.
그리고 compareString에 strs[0].slice(0, size) strs의 0번째에 0부터 size가 까지 잘라서 넣는다.
그 다음에 반복문을 돌려서 i가 1부터 strs 배열의 길이까지 반복문을 돌린다.
만약 !strs[i].startsWith(compareString) compareString으로 strs배열의 해당 인덱스의 요소가 시작하지 않으면 return false를 시작하면 return true를 반환한다.
그리고 getPrefix 함수로 넘어가서 strs가 하나도 들어있지 않을때는 ''을 반환하고 아니면 계속 진행
let minlength = 34124421312; minlength는 그냥 임의로 가장 큰 값을 주었다. strs 배열의 요소중 가장 짧은것의 길이를 말함!
그 후 또 0부터 strs 배열의 길이까지 반복문을 돌려서 만약 strs[i]번째의 길이가 minlength 보다 작으면 minlength에 strs[i]의 길이를 넣어준다. 반복문을 돌면서 minlength가 항상 가장 작은 길이를 갖도록 하기 위함!
그리고 s = 1, e = minlength, mid; let anslength = 0; 필요한 변수들을 설정해주고 여기서
let anslength = 0; 이건 우리가 찾을 공통된 문자의 길이!
while로 또 반복문을 돌려서 s와 e를 더한값에 반을 나누고 Math.floor로 소수점을 날리면 mid에 저장한다.
그리고 위에서 만든 함수 checkPrefix를 사용해 mid와 strs를 넘겨주게 되고 만약 true를 반환하면 s에 mid + 1을 넣고 anslength는 mid과 비교해서 더 큰값으로 갱신해준다. 만약 checkPrefix에서 false를 반환하면 e에 mid - 1을 넣어준다.
이렇게 다 거치고 나면은 변수 answer에 0부터 우리가 구한 anslength까지 strs[0]을 slice 해서 저장하고 이를 최종적으로 반환하면 공통된 접미사?를 반환하는 함수 완성
느낀점: 바이너리 서치에 대해서 더 공부해봐야 겠다... slice 잘린 위치가 계속 햇갈린다.
