JavaScript Algorithm - LPS(Longest Prefix which is also Suffix)

 

 

문제 설명 :  문자열을 입력받은 뒤 다음조건을 만족하는 LPS(Longest Prefix which is also Suffix)를 찾아서 그 길이를 리턴하기

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

 

네이버 언어사전에서 찾은 접두어, 접미어

접두-어 接頭語 :  파생어를 만드는 접사로, 어근이나 단어의 앞에 붙어 새로운 단어가 되게 하는 말. ‘맨손’의 ‘맨-’, ‘들볶다’의 ‘들-’, ‘시퍼렇다’의 ‘시-’ 따위가 있다. 

접미-어 接尾語 :  파생어를 만드는 접사로, 어근이나 단어의 뒤에 붙어 새로운 단어가 되게 하는 말. ‘선생님’의 ‘-님’, ‘먹보’의 ‘-보’, ‘지우개’의 ‘-개’, ‘먹히다’의 ‘-히-’ 따위가 있다.

 

 

입력

인자 1 : str

• string 타입의 임의의 알파벳 소문자 문자열 
• str.length는 60,000 이하

출력

• number 타입을 리턴해야 합니다.

 

입출력 예시

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 입니다.


output = LPS('aaaa');
console.log(output); // --> 2

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



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



output = LPS('abcab');
console.log(output); // -->2



output = LPS('babbabbabb');
console.log(output); // --> 4

 

 

문제풀이 설명 
3가지 방법이 있지만 가장 쉽고 짧은 것은 정규표현식이다.

첫번째와 두번째 코드를 먼저 살펴보자.

문제풀이1

수도코드 

1. 문자열 길이가 2 미만일 경우 0을 반환한다.
2. leftIdx =0을 반환한다. rightIdx는 문자열 길이가 홀수일 때 반올림하기 위해 Math.ceil을 사용한다. 
3. rightIdx가 str.length(입력받은 문자열)보다 작은 경우 무한루프 
4. 입력받은 문자열에서 [leftIdx]와  [rightIdx]가 같을 경우 leftIdx, rightIdx 각각 ++로 증가
5. leftIdx와 rightIdx가 같지 않을 경우 rightIdx에 rightIdx - lefIdx +1의 값을 대입하고 leftIdx에는 0을 저장
6. LPS가 없으면 0을 반환하기 

const LPS = function (str) {
    if (str.length < 2) return 0;
  
    // 문자열을 두 부분으로 나누고
    // 각 부분의 첫 인덱스를 저장
    let leftIdx = 0;
    // 문자열의 길이가 홀수일 수 있으므로, 올림한다.
    let rightIdx = Math.ceil(str.length / 2);
   
    //console.log("leftIdx",leftIdx)
    console.log("before",str.length / 2)
    console.log("rightIdx",rightIdx)
    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;
        leftIdx = 0;
      }
    }
  
    // LPS가 없는 경우
    return leftIdx;
  };

 

 

문제풀이2

수도코드

1. 문자열 길이가 2 미만일 경우 0을 반환한다.
2. 문자열을 두 부분으로 나누고 왼쪽 마지막 인덱스와 오른쪽 첫 인덱스를 저장 
3. 가장 긴 LPS 후보검사 
4. matched === true일 경우 halfSize - offset 
5. LPS가 없으면 0을 반환 

const LPS = function (str) {
    if (str.length < 2) return 0;
  
    // 문자열을 두 부분으로 나누고
    // 부분 문자열을 쉽게 구하기 위해
    // 왼쪽 부분의 마지막 인덱스와 오른쪽 부분의 첫 인덱스를 저장
  
    let halfSize = Math.floor(str.length / 2);
    // 문자열의 길이가 홀수일 수 있으므로, 올림한다.
    let rightStart = Math.ceil(str.length / 2);
  
    // 가장 긴 LPS 후보부터 차례대로 검사한다
    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;
  };

 

 

문제풀이3

정규표현식으로 풀이

수도코드 
1. result 변수에 입력받은 문자열이 정규식과 매치되는 부분을 검색하기 str.match 

2. /^(\w*).*\1$/ 정규표현식을 세우기 

3. 정규표현식과 일치하면 일치하는 전체문자열을 첫 번째 요소로 포함하는 Array를 반환함

  const LPS = (str) => {
    const result = str.match(/^(\w*).*\1$/);
    console.log("result",result)
    return result[1].length;
  };

 

console.log 결과

result [ 'abbbcc', '', index: 0, input: 'abbbcc', groups: undefined ]
0
result [ 'aaaa', 'aa', index: 0, input: 'aaaa', groups: undefined ]
2
result [ 'aaaaa', 'aa', index: 0, input: 'aaaaa', groups: undefined ]
2
result [ 'aaaa', 'aa', index: 0, input: 'aaaa', groups: undefined ]
2
result [ 'a', '', index: 0, input: 'a', groups: undefined ]
0
result [ 'abbbcc', '', index: 0, input: 'abbbcc', groups: undefined ]
0
result [ 'abcab', 'ab', index: 0, input: 'abcab', groups: undefined ]
2
result [
  'babbabbabb',
  'babb',
  index: 0,
  input: 'babbabbabb',
  groups: undefined
]
4