[프로그래머스][LEVEL3] 가장 긴 팰린드롬

# 문제 원문

https://programmers.co.kr/learn/courses/30/lessons/12904

코딩테스트 연습 - 가장 긴 팰린드롬

앞뒤를 뒤집어도 똑같은 문자열을 팰린드롬(palindrome)이라고 합니다.
문자열 s가 주어질 때, s의 부분문자열(Substring)중 가장 긴 팰린드롬의 길이를 return 하는 solution 함수를 완성해 주세요.

예를들면, 문자열 s가 "abcdcba"이면 7을 return하고 "abacde"이면 3을 return합니다.

제한사항

• 문자열 s의 길이 : 2,500 이하의 자연수
• 문자열 s는 알파벳 소문자로만 구성

---

입출력 예

s / answer

"abcdcba"	7
"abacde"	3

# 문제 풀이

 

입력 받은 문자열s 에서 가장 긴 팰린드롬 즉 회문을 찾아서 그 길이를 반환하는 문제이다. dp를 이용하면 간단하게 풀 수 있다. 봐야할 조건은 1. 같은 문자로 이루어진 회문 2, 하나의 문자를 기준으로 서로 대칭되는 회문 3, 완전히 대칭되는 회문이다. 회문은 3가지 경우로 이루어져 있을 수 있으므로 문자열 s를 순회하면서 3가지 경우에 해당하는 회문의 길이가 최대 몇인지 비교해가며 구하면된다. 

 

# 솔루션 플로우

1. 입력 받은 s의 길이 만큼 반복한다.

2. left, right, count를 통해서 3가지 종류의 회문의 길이를 구한다.

3. 구해진 state를 result와 비교하여서 크면 result에 대입해준다.

4. 구해진 result를 반환한다.

1. 반복문을 활용한 풀이

function solution(s) {
    let result = 1;

    for (let idx = 0; idx < s.length; idx++) {
        let count = 1;
        while (idx > 0) {
            let left = idx - 1;
            let right = idx + count;
            if (s[left] === s[right]) {
                while (s[left - 1] === s[right + 1]) {
                    if (left - 1 < 0 || right + 1 >= s.length) break;
                    left--;
                    right++;
                }
            } else {
                left = 0;
                right = 0;
            }
            const state = Math.max(right - left + 1, count);
            result = result > state ?
                result :
                state;

            if (s[idx] !== s[idx + count]) break;
            count++;
        }
    }

    return result;
}