📌 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 입니다.
문제엔 나와있지 않았지만 빈 문자열을 받았을땐 0을 출력해야 했기 때문에 일단 그 경우를 제외하여 주고, prefix와 suffix를 이용해야 할것 같아서 일단 변수로 설정했다. 하지만 거기서 탈락...ㅎ
let prefix = str.slice(0,i) let suffix = str.slcie(2) if(str.length <=1 ) { return 0 } }//....?
게다가 advanced 문제에서 시간 복잡도를 개선하는 방법도 알아내라고 했다.(이건 어려우니 레퍼코드를 보며 공부하는 것에 초점을 두라고 했다.
☑ 다른 접근방법
구글링해서 얻어낸 다른 방법은 처음 내가 접근했던 prefix와 suffix를 이용하는 것이었다. 빈문자열을 할당한다. 그리고 반복문을 돌린다. 그 반복문 내에서 접두어와 접미어의 변수를 선언 할당한다.
그리고 접두어와 접미어가 같을 때 prefix를 재할당한다.
let resultStr = '';
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) {
resultStr = prefix;
}
};
return resultStr.length;
};
☑ 정규식 활용방법
단 세줄만에 끝내버리는 마법의 코드 같았지만 시간복잡도는 개선하지 못한다.
const LPS = function (str) { //TODO: 여기에 코드를 작성합니다. //2) 정규식 활용방법 const result = str.match(/(\w*).*\1/); return result[1].length; }
- String.match() 메서드 : 인자로 들어오는 정규식과 문자열을 일치시킨 값을 Array로 반환한다.
- \w : 반복된() word. 알파벳, 숫자, _ 중의 한 문자임을 의미
- \1 : \n은 정규식 내부의 n번째 괄호에서 대응된 부분에 대한 역참조라고 한다.(n은 양의 정수)
출처
MDN 정규 표현식에서는 정규식 리터럴(슬래쉬"/"로 감싸는 패턴)을 사용하는 방법은 다음과 같다고 표현하고 있다.
var re = /ab+c/;
\n은 여기선 n===1 이니까 정규식 내부의 1번째 괄호에서 대응된 부분에 대한 역참조.
advanced를 이해하는 건 일단 주말로 미뤄둬야겠다ㅠㅠ
