[코테연습] 가장 긴 팰린드롬

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

프로그래머스

 

문제 타입

• 문자열 처리
• 동적 계획법 (Dynamic Programming)
• 팰린드롬 문제

---

문제 분석

• 문자열 s에서 가장 긴 팰린드롬 부분 문자열의 길이를 구하는 문제.
• 팰린드롬이란, 앞에서 읽으나 뒤에서 읽으나 동일한 문자열을 의미.
• 중요한 조건:
  1. 팰린드롬의 길이가 1인 경우는 모든 단일 문자.
  2. 길이가 2인 경우는 양 끝 두 문자가 동일한 경우.
  3. 길이가 3 이상인 경우는 양 끝 문자가 동일하고, 내부 문자열도 팰린드롬이어야 함.

---

문제 풀이

1. 동적 계획법 테이블 정의

• isPalindrome[i][j]: 문자열 s[i:j+1]이 팰린드롬인지 여부를 저장하는 2차원 배열.
• 초기 값:
  • isPalindrome[i][i] = True (길이 1)
  • isPalindrome[i][i+1] = True if s[i] == s[i+1] (길이 2)

2. 알고리즘 설계

1. 길이 1과 2 초기화:
   • 모든 단일 문자는 팰린드롬.
   • 인접한 두 문자가 같다면 팰린드롬.
2. 길이 3 이상 처리:
   • 문자열 s[start:end+1]이 팰린드롬인지 확인하려면:
     • 양 끝 문자 s[start]와 s[end]가 같아야 함.
     • 내부 문자열 s[start+1:end]이 팰린드롬이어야 함 (isPalindrome[start+1][end-1]이 True).
3. 최대 길이 갱신:
   • 팰린드롬일 때 현재 길이를 저장하여 최대 길이를 갱신.

3. 시간복잡도

• O(n²): 문자열 길이가 n일 때, 모든 가능한 부분 문자열에 대해 O(n) 반복.

4. 구현

• 2차원 배열을 활용한 동적 계획법을 통해, 모든 길이에 대해 팰린드롬 여부를 계산.

 

> java

 

import java.util.*;

class Solution {
    public int solution(String s) {
        int answer = 0;  // 가장 긴 팰린드롬 부분 문자열의 길이를 저장할 변수
        int n = s.length();  // 문자열의 길이

        // isPalindrome[i][j]: s[i:j+1] 부분 문자열이 팰린드롬인지 여부를 저장
        boolean[][] isPalindrome = new boolean[n][n];
        answer = 1;  // 최소 길이 1의 팰린드롬 (모든 단일 문자는 팰린드롬)

        // 길이 1인 경우, 모든 단일 문자는 팰린드롬으로 설정
        for (int i = 0; i < n; i++) {
            isPalindrome[i][i] = true;
        }

        // 길이 2인 경우, 연속된 두 문자가 같으면 팰린드롬으로 설정
        for (int i = 0; i < n - 1; i++) {
            if (s.charAt(i) == s.charAt(i + 1)) {
                isPalindrome[i][i + 1] = true;  // s[i:i+2]는 팰린드롬
                answer = 2;  // 팰린드롬의 길이를 갱신
            }
        }

        // 길이 3 이상인 경우
        // i는 부분 문자열의 길이 (3부터 n까지 증가)
        for (int i = 3; i <= n; i++) {
            // start는 부분 문자열의 시작 인덱스
            for (int start = 0; start <= n - i; start++) {
                int end = start + i - 1;  // 부분 문자열의 끝 인덱스

                // s[start]와 s[end]가 같고, 내부 부분 문자열이 팰린드롬이면
                if (s.charAt(start) == s.charAt(end) && isPalindrome[start + 1][end - 1]) {
                    isPalindrome[start][end] = true;  // s[start:end+1]은 팰린드롬
                    answer = i;  // 팰린드롬의 최대 길이를 갱신
                }
            }
        }

        // 가장 긴 팰린드롬 부분 문자열의 길이를 반환
        return answer;
    }
}

 

> python

 

def solution(s):
    answer = 1

    n = len(s)
    
    # length == 1
    isPalindrome = [[False] * n for _ in range(n)]
    for i in range(n) :
        isPalindrome[i][i] = True
    
    
    # length == 2
    for i in range(n-1) :
        if s[i] == s[i+1] :
            isPalindrome[i][i+1] = True
            answer = 2
        
    # length >= 3
    for i in range(3, n+1) :
        for start in range(n-i+1) :
            end = start + i - 1
            if s[start] == s[end] and isPalindrome[start+1][end-1] :
                isPalindrome[start][end] = True
                answer = i
    
    
    return answer