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

woolee의 기록보관소·2023년 2월 4일

Algorithms 알고리즘개념정리

알고리즘 문제풀이

목록 보기

156/178

문제 출처

프로그래머스 lev3 - 가장 긴 팰린드롬

나의 풀이

1차시도(84.7/100)

효율성 1개가 시간초과가 뜬다.

function rev(str){
  let r = ''
  for(let i=str.length-1; i>=0; i--) r += str[i]
  return r 
}
function solution(s){
  let ans = s.length 
  let flag = true 
  
  while(flag){
    let sub = ans%2==0 ? ans/2 : Math.floor(ans/2)

    for(let i=0; i<=s.length-sub*2; i++){ // if(i+sub*2 <= s.length)
      let front = s.slice(i, i+sub)
      let back = ans%2==0 
        ? s.slice((i)+sub, (i)+sub*2) 
        : s.slice((i+1)+sub, (i+1)+sub*2) 
    
      if(front === rev(back)) {
        flag = false 
        break 
      }
    }
    if(flag) ans--
  }
  return ans 
}

// console.log(solution("abcdcba")) // 7 
// console.log(solution("abacde")) // 3

다른 풀이

나는 팰린드롬 여부를 너무 어렵게 체크했다.

팰린드롬(앞뒤를 뒤집어도 똑같은 문자열) 체크 로직을 다음과 같이 구현한다.

시작점(start)과 끝점(end)을 설정하고,
=> 시작점과 끝점이 다르면 팰린드롬이 아니다.
=> 시작점과 끝점이 같으면 시작점++, 끝점--해줘서 계속 팰린드롬을 체크한다.

answer를 최대값(s.length)으로 설정해놓고
해당 answer이 팰린드롬이면 while문을 종료하지만, 아니라면 answer를 감소시켜 범위를 줄여나간다.

function isPalindrom(left, right, s){
  while(left < right){
    if(s[left++] !== s[right--]) return false 
  }
  return true 
}

function solution(s) {
  let answer = s.length 

  while(answer){
    let start = 0 
    let end = answer - 1 

    while(end < s.length){
      if(isPalindrom(start++, end++, s)) return answer  
    }
    answer-- 
  }
  return answer  
}

다른 풀이 (dp)

출처 : [프로그래머스] LV.3 가장 긴 팰린드롬 (JS)

어떤 문자열이 팰린드롬인지 체크할 때, 양 끝점에서 시작해서 범위를 좁혀가며 하나하나 일치하는지 체크한다. 이를 일반화하면 팰린드롬은 다음과 같은 조건을 요구한다.

양 끝의 문자가 서로 일치
양 끝 사이 문자열들이 팰린드롬이면 된다.
혹은 양 끝 사이 문자열의 길이가 0 또는 1면 역시 팰린드롬이 된다.

양 끝점에서 시작해서 범위를 좁혀가며 하나하나 일치하는지 체크하는 과정은,
반대로 생각하면 가운데에서 시작해서 재귀를 통해 거슬러 올라오며 팰린드롬인지 체크하는 것과 같은 의미를 갖는다.

길이 1에서부터 현재 길이까지 구한다고 가정하면,
이전 결과(1부터 n-1까지)를 현재 검색(n)에 활용하는 것과 같다.

function solution(s){
  if (s === s.split("").reverse().join("")) {
    return s.length
  } else {
    let A = solution(s.substring(0, s.length-1))
    let B = solution(s.substring(1, s.length))
    return Math.max(A, B)
  }
}

이러한 재귀 과정에서는 중복이 발생할 것이므로,
이전 값들을 구할 때 미리 저장해 놓음으로써 중복을 막을 수 있다.
또한 이러한 재귀 형태를 띠면 dp를 활용할 수 있는 조건을 만족한다고 볼 수 있다.

점화식 dp[i][j] : 시작점 i에서 끝점 j까지의 문자열이 팰린드롬이면 true, 아니면 false

let answer = 1;
const len = s.length;
const dp = new Array(len).fill().map(_ => new Array(len).fill(false));

점화식의 초기화는 이렇게 할 수 있다.

길이 1 (dp[i][i]) : 자기 자신은 무조건 팰린드롬이다.
길이 2(dp[i][i+1]) : i에서 i+1까지는 바로 체크해줄 수 있으므로 초기화할 수 있다.

for(let i = 0; i < len; i++) {
  dp[i][i] = true;
}

for(let i = 0; i < len - 1; i++) {
  if(s[i] === s[i+1]) {
    dp[i][i+1] = true;
    answer = 2;
  }
}

여기까지 하면 위에서 정의한 팰린드롬 조건 중
양 끝점 문자가 일치하고 && 내부 문자열 길이가 0이거나 1인 경우를 미리 초기화한 셈이다.

길이 3부터 시작하는데, 위에서 정의한 팰린드롬 조건을 다음과 같이 구현한다.

시작지점 start, 끝점 end 일 때, 일단 s[start] === s[end]이면서
dp[start+1][end-1]==true이면 양 끝점 사이의 내부 문자열이 팰린드롬을 만족한다는 의미를 갖는다.

for(let i = 3; i <= len; i++) {
  for(let start = 0; start <= len - i; start++) {
    const end = start + i - 1;
    if(s[start] === s[end] && dp[start+1][end-1]) {
      dp[start][end] = true;
      answer = Math.max(answer, i);
    }
  }
}

전체 코드

function solution(s) {
  let answer = 1;
  const len = s.length;
  const dp = new Array(len).fill().map(_ => new Array(len).fill(false));
  
  for(let i = 0; i < len; i++) {
    dp[i][i] = true;
  }
  
  for(let i = 0; i < len - 1; i++) {
    if(s[i] === s[i+1]) {
      dp[i][i+1] = true;
      answer = 2;
    }
  }
  
  for(let i = 3; i <= len; i++) {
    for(let start = 0; start <= len - i; start++) {
      const end = start + i - 1;
      if(s[start] === s[end] && dp[start+1][end-1]) {
        dp[start][end] = true;
        answer = Math.max(answer, i);
      }
    }
  }
  
  return answer;
}