알고리즘 문제 풀이(프로그래머스 - 가장 긴 팰린드롬)

프로그래머스 LEVEL 3(가장 긴 팰린드롬)

• 사용 언어 : javascript

• 해결 날짜 : 2022-12-22

• 해결 방법 :

  • dp를 통해 문제 해결
    • x 인덱스로부터 y인덱스까지의 팰린드롬 여부를 저장할 dp 배열 초기화
    • 인덱스 0 ~ s.length - 1 까지 돌며
      • 길이가 1인 경우(dp[i][i]) true로 업데이트
      • 길이가 2인 경우(dp[i][i + 1]) true로 업데이트 및 answer 2로 변경
    • 길이가 3 이상인 경우를 체크하기 위해 3 ~ s.length 까지 반복
      • left가 될 수 있는 값은 0 ~ s.length - len
      • right는 left + len - 1
      • 이 때 left의 값과 right의 값이 같고, 그 사이의 dp값이 참이면
        • dp[left][right] true로 업데이트
        • answer과 비교하여 큰 값으로 설정

• 회고 :

  • x

• 코드

  function solution(s) {
    let answer = 1;
    const dp = Array.from({ length: s.length }, () => Array(s.length).fill(false));
  
    for (let i = 0; i < s.length - 1; i++) {
      dp[i][i] = true;
      if (s.charAt(i) === s.charAt(i + 1)) {
        dp[i][i + 1] = true;
        answer = 2;
      }
    }
    dp[s.length - 1][s.length - 1] = true;
  
    for (let len = 3; len <= s.length; len++) {
      for (let left = 0; left <= s.length - len; left++) {
        const right = left + len - 1;
        if (s.charAt(left) === s.charAt(right) && dp[left + 1][right - 1]) {
          dp[left][right] = true;
          answer = Math.max(answer, len);
        }
      }
    }
  
    return answer;
  }
  

• 출처: 프로그래머스 코딩 테스트 연습, https://school.programmers.co.kr/learn/challenges