Toy 문제 19

문제

문자열을 입력받아 다음의 조건을 만족하는 LPS*를 찾아 그 길이를 리턴해야 합니다.

• LPS: 주어진 문자열의 가장 긴 접두어이자 접미어(Longest Prefix which is also Suffix)
• non-overlapping: 접두어와 접미어는 서로 겹치는 부분이 없어야 합니다. 다시 말해, prefix와 suffix는 문자열의 동일한 인덱스에 위치한 문자를 요소로 가지면 안 됩니다.

let output = LPS('abbbcc');
console.log(output); // --> 0

output = LPS('aaaa');
console.log(output); // --> 2
// prefix: str.slice(0, 2)
// suffix: str.slice(2)
// non-overlapping 조건이 없는 경우 정답은 4 입니다.

output = LPS('aaaaa');
console.log(output); // --> 2
// prefix: str.slice(0, 2)
// suffix: str.slice(3)
// non-overlapping 조건이 없는 경우 정답은 5 입니다.

Advanced

• LPS를 계산하는 효율적인 알고리즘(O(N))이 존재합니다. 쉽지 않기 때문에 바로 레퍼런스 코드를 보고 이해하는 데 집중하시기 바랍니다.
• 정규식(regular expression)을 활용하면 아래처럼 간단하게 구현할 수 있습니다. 정규식에 대해서 학습하시기 바랍니다. (참고사이트)

 

수도코드(해석)

알고리즘 O(N) 이여서 단순히 반복문 돌려서 사용을 하였는데 모두 통과가 되었다.. 심지어 레퍼런스 코드도 어렵다고 하는데..

레퍼런스처럼 사용하면 더 좋은 이유가 있을까..? 문제 내신분이 더 어렵게 생각하신건가 싶기도 하다

 

문자열의 어느 한 기준으로 앞과 뒤가 겹치는 부분이 없어야 하기 때문에

문자열의 기준을 앞에서 부터 두고 기준을 차례대로 옮기면서 조건을 만족할 시 그 결과 값을 리턴하는 방식으로 코드를 짰습니다.

 

 

코드

const LPS = function (str) {
  // TODO: 여기에 코드를 작성합니다.
  let result = '';
  for (let i = 0; i <= str.length / 2; i += 1) {
    let prefix = str.slice(0, i);
    let suffix = str.slice(str.length - i);
    if (prefix === suffix) {
      result = prefix;
    }
  };
  return result.length;
};

 

 

Reference Code

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]) {
      // 가장 단순한 경우를 생각해보면, 쉽게 이해할 수 있다.
      // 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 매칭을 하는 경우이다.
        //
        // lps가 존재하지 않는 경우이다.
        lps[rightIdx] = 0;
        rightIdx++;
      }
    }
  }
  const res = lps[lps.length - 1];
  return res > str.length / 2 ? Math.floor(str.length / 2) : res;
};