[프로그래머스] Lv3. 가장 긴 팰린드롬- JavaScript

문제분류 : 코팅테스트 연습

난이도 : Level 3

출처 : 프로그래머스 - 가장 긴 팰린드롬

문제

제한사항

📌 내가 생각한 풀이

최대 Len부터 문자열을 구하고, 처음 글자와 마지막 글자가 다르면 바로 out, 같으면, 두번째글짜와, 마지막에서 두번쨰 글짜가 같은지 확인!

아니면, 그다음 최대 len-1하여 같은 과정 반복!
예를들어 "abacde"라고 하자
1. 가장 긴 문자 -> "abacde"
2. 첫 글자: a, 마지막 글자 : e -> out!!!
3. 그 다음 긴 문자 -> "abacd", "bacde"
4. "abacd"의 첫 글자 : a, 마지막 글자: d -> out!!!
5. "bacde"의 첫 글자 : b, 마지막 글자 : e -> out!!!
같은 과정 반복!!

const check = (str) =>{
    let mid = Math.floor(str.length/2);
    for(var i =0; i<mid; i++){
        if(str[i] !== str[str.length-i-1]) return false;
    }
    return true;
}

function solution(s)
{
    var answer = 0;
    for(var i=s.length; i>=1; i--){
        for(var k = 0; k<=s.length-i; k++){
            let slice= s.slice(k,k+i);
            let checked = check(slice);
            if(checked) return slice.length
        }
    }
}

📌 느낀점

예전 학교에서 알고리즘시간에 배웠던 방식이었다. 팰린드롬이 되려면 가장 첫번째 글자와, 마지막 글짜가 다르면 안되므로, 바로 다음 과정으로 넘어가면 된다. 시간 복잡도는 O(n)까지 줄일 수 있었다.