프로그래머스 [Lv. 3] 가장 긴 팰린드롬 {언어 : JavaScript}

문제 링크

https://school.programmers.co.kr/learn/courses/30/lessons/12904?language=javascript

프로그래머스

정답 코드

function solution(s)
{
    let answer = 1;
    const lenS = s.length;
    // 홀수 펠린드롬
    for (let i = 1; i < lenS; i++) {
        let [l, r] = [i-1, i+1];
        let currentLength = 1;
        while (0 <= l && r < lenS) {
            if (s[l] == s[r]) {
                currentLength += 2;
                l -= 1;
                r += 1;
            } else {
                break;
            };
        };
        if (currentLength > answer) {
            answer = currentLength;
        };
    };
    
    // 짝수 펠린드롬
    for (let j = 0; j < lenS-1; j++) {
        let [l, r] = [j, j+1];
        let currentLength = 0;
        while (0 <= l && r < lenS) {
            if (s[l] == s[r]) {
                currentLength += 2;
                l -= 1;
                r += 1;
            } else {
                break;
            };
        };
        if (currentLength > answer) {
            answer = currentLength;
        };
    };
    
    return answer;
}

풀이 방법

1. 홀수 펠린드롬과 짝수 펠린드롬을 나눈다.
2. 중심 i, j를 기준으로 확장하면서 펠린드롬인지 확인한다.
3. 현재 길이를 answer와 비교해서 큰 수를 치환한다.
4. answer를 반환하면 끝!

느낀점

• 중심 확장 방법이라고 하는데 사실 그냥 해봤다.
• 중심을 기점으로 퍼져나가면서 탐색하면 될 것이라고 생각했다.
• s의 길이가 2500이라 O(N^2)도 실행 가능해 보였다.