가장 긴, 접두어이면서 동시에 접미어인 부분 문자열의 최대 길이 구해라(접두어와 접미어는 문자열 내에서 겹치면 안된다.)
입출력 예시
내가 작성한 코드(테스트케이스가 다 통과됐다가 안됐다가 이랬음)
const LPS = function (str) {
// TODO: 여기에 코드를 작성합니다.
//입략: 문자열. 알파벳 소문자 이어붙인것
//특이한 입력: 빈 문자열도 올수있음(이때는 0을 출력할 것) 길이 1 이하의 문자열 입력 시 0을 리턴
//출력: 숫자- 가장 긴 접두어이면서 동시에 가장 긴 접미어의 길이.
// 접두어 접미어는 서로 겹치지 않기
//예시 이해하기
/*
1. abb bcc
접두어로는 a, ab, abb
접미어로는 c, cc, bcc
교집합이 없다 : 0
2. aaaa
접두어로는 a, aa
접미어로는 a, aa
교집합은 aa니까 최대 길이는 2
3. aaaaa
접두어로는 a, aa, aaa
접미어로는 a, aa
교집합은 aa니까 최대 길이는 2
위와 같이 나오는 이유는 뒤와 앞에서 출발했을 때 겹치면 안되기 때문이다.
일단 글자를 반으로 쪼개야 한다. 각각의 left, rught라고 부르자.
짝수인 경우에는 이 둘의 길이가 같고
홀수인 경우는 이 둘 중 하나가 나머지보다 1 더 길다.
일단 부분 문자열을 구해놔야 비교할 수 있음
left쪽에서 부분문자열 구하기
글자의 절반 부분 순회
반복문 외부에 변수선언: ''과 []
첫번째단계: 빈 문자열 푸시
두번째단계: 문자열 1개 붙인 후 푸시
세번째단계: 문자열 2개 붙인 후 푸시
...
6글자인 경우 절단은 3글자니까 총 4번 반복.
7글자인 경우 절반은 3글자라 치고 총 4번 반복.
일반화: Math.floor(str.length / 2) + 1번 반복 순회
right쪽에서 부분 문자열 구하기
글자의 절반 부분 순회
반복문 외부에 변수 선언: ''과 []
첫번째단계: 빈 문자열 푸시
두번째단계: 맨 마지막 문자 푸시
세번째단계: 마지막에서 2번째와 마지막 글자 합쳐서 푸시
...
6글자인경우 절반은 3글자니까 총 4번 반복
7글자인경우 절반은 3글자라 하자. 가운데는 길이가 안맞아서 안돼. 총 4번 반복.
이제 가능한 모든 접두어 접미어를 구했다.
교집합 구해야 한다.
예) ['', 'a','aa'] ['', 'a', 'aa','aaa']
교집합 구한 뒤 리듀스로 가장 긴 문자열의 길이를 리턴한다.
*/
if(str.length <= 1) return 0;
//절반 문자열 구하기
let mid = Math.floor(str.length / 2)
let left = str.slice(0,mid);
let right = str.slice(mid);
//각각의 부분 문자열 구하기
const pre = []
const suf = []
let count = 0;
let i = 0;
while(count < mid + 1){
if(i === 0){
pre.push(left.slice(0,i))
suf.push(right.slice(0,-i))
}else{
pre.push(left.slice(0,i))
suf.push(right.slice(-i))
}
count++;
i++;
}
//교집합 구하기
let common = pre.filter(x => suf.includes(x));
//리듀스로 가장 긴 문자열 길이 리턴 : 이거로 하면 통과가 다됐다가 안됐다가 왔다갔다함
// return common.reduce((acc,cur) => {
// if(acc < cur.length){
// return cur.length;
// }else{
// return acc;
// }
// },0)
return common[common.length -1].length // 이것도 통과 다됐다가 안됐다가 왔다갔다함
};
레퍼런스
1번과 2번의 풀이과정은 그 원리가 비슷하다.
절반으로 나누어 출발하는데 마지막 솔루션은 두개의 인덱스가 왼쪽에 둘 다 치우쳐져 있다.
// naive solution
// const LPS3 = function (str) {
// if (str.length < 2) return 0;
// // 문자열을 두 부분으로 나누고
// // 부분 문자열을 쉽게 구하기 위해
// // 왼쪽 부분의 마지막 인덱스와 오른쪽 부분의 첫 인덱스를 저장
// let halfSize = Math.floor(str.length / 2);
// // 문자열의 길이가 홀수일 수 있으므로, 올림한다.
// let rightStart = Math.ceil(str.length / 2);
// // 가장 긴 LPS 후보부터 차례대로 검사한다
//예를 들어 abab의 경우 (a,a) 확인, (b,b) 확인 이렇게 넘어간다.
// for (let offset = 0; offset < halfSize; offset++) {
// let matched = true;
// for (let i = 0; i < halfSize - offset; i++) {
// if (str[i] !== str[rightStart + offset + i]) {
// matched = false;
// break;
// }
// }
// if (matched) return halfSize - offset;
// }
// // LPS가 없는 경우
// return 0;
// };
// naive solution2이거 이해했음
const LPS = function (str) {
if (str.length < 2) return 0;
// 문자열을 두 부분으로 나누고
// 각 부분의 첫 인덱스를 저장
let leftIdx = 0;
// 문자열의 길이가 홀수일 수 있으므로, 올림한다.
let rightIdx = Math.ceil(str.length / 2);
while (rightIdx < str.length) {
if (str[leftIdx] == str[rightIdx]) { 비교 방식은 첫번째 풀이와 동일.
// LPS 검사를 시작한 위치부터 지금까지 계속 같은 경우
// 다음 문자도 같은지 확인하기 위해 인덱스를 이동한다.
leftIdx++;
rightIdx++;
} else {
// leftIdx가 0인 경우, 단순히 rightIdx를 1 증가 (suffix의 시작점을 뒤로 한 칸 이동)
// prefix, suffix가 계속 일치하다가 중간에서 일치하지 않는 경우에도,
// **현재 suffix의 시작점을 뒤로 한 칸 이동**한다. (끝까지 보내줌 => 강제 종료를 위한 이동)
rightIdx = rightIdx - leftIdx + 1; (안 빼주면 if에서 종료됨)
leftIdx = 0;
}
}
// LPS가 없는 경우 및 lps 의 길이 리턴 동시에 함
return leftIdx;
};
// dynamic solution: O(N)
left를 0으로, right를 1로 두고 l과 r이 같아질때까지 r을 계속 증가시킨다.
그러다가 l과 r이 같아지고 r이 length/2이상이면 다음 문자열 검사한다 (l과 r 인덱스 둘 다 증가)
쭉 일치시키다가, 일치하지 않는 문자열이 중간에 나왔다면 완전 실패한 것이기 때문에
계속 0을 배열에 넣어주고있다.(마지막에 0을 리턴하도록)
// non-overlapping 조건을 제거하고 lps를 구한다.
// lps는 주어진 문자열에서 아래 조건을 만족하는 가장 긴 접두어(prefix)의 길이를 의미한다.
// - 해당 접두어는 주어진 문자열의 접미어(suffix)이기도 하다.
// 이때, 문자열 자기 자신은 그 자체로 prefix이자 suffix인데, 이는 고려 대상에서 제외한다.
const LPS = function (str) {
// lps[i]는 0부터 i까지의 부분 문자열, 즉 str.slice(0, i + 1)에서 lps의 길이를 저장한다.
const lps = Array(str.length);
// lps[0]은 길이가 1인 문자열의 lps의 길이이므로 항상 0이다. (자기 자신 포함 금지)
lps[0] = 0;
let leftIdx = 0;
let rightIdx = 1;
// lps[i]를 1부터, 즉 문자열의 길이가 2일때부터 차례대로 구한다.
while (rightIdx < str.length) {
if (str[leftIdx] === str[rightIdx] && rightIdx >= str.length / 2) { //왼쪽 오른쪽 문자가 같다면 lps추가
// 가장 단순한 경우를 생각해보면, 쉽게 이해할 수 있다.
// 1) 길이가 2 경우
// 2) 길이가 3 이상인데 전부 같은 문자인 경우
// 0부터 leftIdx까지 매칭이 되었으므로 매칭된 길이는 leftIdx + 1이다.
leftIdx++;
lps[rightIdx] = leftIdx;
rightIdx++;
} else {
// 중간에 매칭이 되지 않은 경우, leftIdx를 조정한다.
// 현재 lps[0]부터 lps[rightIdx - 1]까지 계산이 완료된 상태이다.
// 처음부터 다시 prefix, suffix 매칭을 하는 것이 원칙이지만
// 앞서 계산한 결과인 lps 배열을 통해 처음으로 되돌아갈 필요는 없다.
// 예. aaabaaaa
// 현재 leftIdx는 2, rigthIdx는 3, lps는 [0, 1, 2]인 상태라고 가정해보자.
// leftIdx가 1일 때까지, 즉 현재 leftIdx 직전(leftIdx - 1)까지는 매칭이 되었다.
if (leftIdx !== 0) {
leftIdx = lps[leftIdx - 1];
// Also, note that we do
// not increment i here
} else {
// rightIdx가 1인 경우, 즉 첫 iteration일 경우
// lps[rightIdx]가 0인 것은 명백하다. (예. ab)
// leftIdx가 0이라는 것은 처음부터 prefix, suffix 매칭을 하는 경우이다.
// 여기서는 rightindex만 증가시켜서 강제 종료한다.
// lps가 존재하지 않는 경우이다.
lps[rightIdx] = 0;
rightIdx++;
}
}
}
const res = lps[lps.length - 1]; //마지막값이 최대다.
return res > str.length / 2 ? Math.floor(str.length / 2) : res;
};
debugger;
LPS("abcckabcdk");
마지막 솔루션 디버거 모습
디버거로 설명해보면, 중간에 실패한 경우에는 left인덱스를 0으로 만들어놓고, 일부러 right랑 비교하여 틀린 결과가 나오게 만든 다음에 right인덱스를 계속 증가시켜서 강제로 종료시키고 있다.
left인덱스는 최대 일치하는 문자열의 길이 - 1까지의 값만 가질 수 있다.
자바처럼 고정된 길이의 배열을 만드는 방법
