[코테] 가장 긴 접두어이자 접미어(LPS)

 

 

문제

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

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

입력

인자 1 : str

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

출력

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

주의사항

• 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)을 활용하면 아래처럼 간단하게 구현할 수 있습니다. 정규식에 대해서 학습하시기 바랍니다. (참고사이트)

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

---

문제 이해

주어진 문자열에서 가장 긴 접두어이자 접미어를 찾아야 하는데, 이때 접두어와 접미어가 겹쳐선 안됩니다.

즉, 문자열의 가운데를 기준으로 접두어와 접미어로 나뉘어야 합니다.

헷갈릴 수 있는게 대칭과는 다른 의미인데 예시로 설명해 보겠습니다.

 

1. 주어진 문자열이 겹치지 않는 접두어와 접미어일 경우:  ABCDABC

2. 주어진 문자열이 가운데를 기준으로 대칭인 경우: ABCDCBA

 

1번처럼 D를 중심으로 접두어와 접미어가 각각 ABC인 문자열 인지를 판별해야 합니다.

 

풀이 💡

const LPS = function (str) {
    let arr = str.split("");
    let count = 0;
    for (let i = 0; i < parseInt(arr.length / 2); i++) {
        if (
            arr.slice(0, i + 1).toString() ==
            arr.slice(arr.length - 1 - i, arr.length).toString()
        ) {
            count=i+1;
        }
    }
    return count;
};

 

문자열을 탐색하기 위해서는 for문을 사용해야 하고 그러기 위해서 배열로 만들어 주고

count라는 변수를 선언하여 가장 길 때의 접두(미)어를 담아 for문이 종료된 후 리턴해야 합니다.

let arr = str.split("");
let count = 0;

 

문자열의 앞부분과 뒷부분만 비교하면 되므로 길이의 절반만큼(parseInt(arr.length/2))만 for문을 실행합니다.

arr.slice(0, i + 1)  가 어려울 수 있는데 문자열의 접두어를 한 글자씩 늘려간다는 의미입니다.

 

ABCDABC를 예시로 들면

i=0 일 때, A

i=1 일 때, AB

i=2 일 때, ABC

arr.slice(arr.length - 1 - i, arr.length) 는 접미어에 해당하는 부분으로 거꾸로 한 글자씩 늘려 간다는 의미입니다.

 

ABCDABC를 예시로 들면

i=0 일 때, C

i=1 일 때, BC

i=2 일 때, ABC

 

i가 0,1일 때에는 다르고 2일 때 같으므로 count는 3이 됩니다.

for (let i = 0; i < parseInt(arr.length / 2); i++) {
        if (
            arr.slice(0, i + 1).toString() ==
            arr.slice(arr.length - 1 - i, arr.length).toString()
        ) {
            count=i+1;
        }
}

 

더 좋은 풀이법이나 궁금한 점이 있으시면 댓글 부탁드립니다. 감사합니다.