[프로그래머스/CPP/JS] 가장 긴 팰린드롬

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

1. 문제

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

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

2. 제한사항

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

3. 풀이

• 직접 반복문 돌면서 구해줬다.
• 시간 초과 날 줄 알았는데 안 났다.

4. 처음 코드와 달라진 점

• 예시 문제에서는 특정 문자 기준 앞, 뒤가 같은 (총 문자 수가 홀수인) 문자만 있어서 홀수만 찾아서 틀렸다.
• 기준이 숫자가 아니라 숫자 사이인 총 문자 수가 짝수인 경우도 찾아 줘야 했다.
• 어떻게 할까 고민하다가 그냥 for 반복문 하나 더 써줬다. 통과했다.

5. 코드

#include <iostream>
#include <string>
#include <algorithm>

using namespace std;
int solution(string s){
    int answer=1;
    int len = s.size();
    
    for(int i=1; i<len-1; i++){
        int count=0;
        int maxLen = min(i, len-i+1);
        
        for(int j=1; j<=maxLen; j++){
            if(s[i-j] != s[i+j]) break;
            count++;
        }
        
        answer = max(answer, count*2+1);
    }
    
    for(int i=0; i<len-1; i++){
        int count=0;
        int maxLen = min(i, len-i-2);
        
        for(int j=0; j<=maxLen; j++){
            if(s[i-j] != s[i+j+1]) break;
            count++;
        }
        
        answer = max(answer, count*2);
    }

    return answer;
}

6. 코드(JS)

function solution(s) {
  const isPalindrome = word => {
    let left = 0;
    let right = word.length - 1;

    while (left < right) {
      if (word[left++] !== word[right--]) return false;
    }
    return true;
  };

  const len = s.length;
  for (let i = len; i > 1; i--) {
    for (let j = 0; j <= len - i; j++) {
      if (isPalindrome(s.slice(j, j + i))) return i;
    }
  }

  return 1;
}