가장 긴 팰린드롬

문제

문자열 s가 주어질 때, s의 부분 문자열(Substring) 중 가장 긴 팰린드롬의 길이를 구하는 프로그램을 작성하는 문제입니다. 팰린드롬이란 앞뒤를 뒤집어도 똑같은 문자열을 의미합니다.

• 입력: 알파벳 소문자로만 이루어진 문자열 s (길이 2,500 이하)
• 출력: 가장 긴 팰린드롬 부분 문자열의 길이

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

풀이 1: 완전 탐색 및 길이 가지치기 (Brute Force)

이중 반복문을 사용하여 가능한 모든 부분 문자열을 추출하고, 이를 뒤집었을 때 원본과 동일한지 확인하는 직관적인 방식입니다.

• 탐색 최적화 (가지치기): 시작 인덱스 i와 끝 인덱스 j를 기준으로 부분 문자열의 길이는 j - i가 됩니다. 만약 이 길이가 현재까지 발견한 가장 긴 팰린드롬의 길이(ans)보다 작거나 같다면, 검사할 필요가 없으므로 continue를 통해 불필요한 문자열 추출과 뒤집기 연산을 생략합니다.
• 팰린드롬 판별: 잘라낸 부분 문자열(tmp)을 StringBuilder 객체에 담고 reverse() 메서드를 호출하여 뒤집은 뒤 원본과 비교합니다.
• 한계점: 가지치기를 통해 연산량을 크게 줄였지만, 최악의 경우 부분 문자열 생성과 뒤집기 연산으로 인해 O(N^3)에 가까운 시간 복잡도를 가질 수 있어 문자열 길이가 최대 2,500일 때 시간 초과가 발생합니다.

코드 1

class Solution {
    public int solution(String s) {
        int ans = 1;
        
        for (int i = 0; i < s.length(); i++) {
            for (int j = i + 1; j <= s.length(); j++) {
                // 현재 최대 길이보다 짧거나 같은 부분 문자열은 검사 패스 (가지치기)
                if (j - i <= ans) continue;
                
                String tmp = s.substring(i, j);
                StringBuilder sb = new StringBuilder(tmp);
                
                // 뒤집은 문자열과 원본이 동일한지 비교
                if (tmp.equals(sb.reverse().toString())) {
                    ans = Math.max(ans, tmp.length());
                }
            }
        } 
        
        return ans;
    }
}

풀이 2: 중심 확장(Expand Around Center) 투 포인터 탐색

이중 반복문으로 모든 부분 문자열을 만들어보는 기존 방식의 시간 초과 문제를 O(N^2)으로 최적화하기 위해, 팰린드롬의 중심에서부터 양옆으로 퍼져나가며 검사하는 투 포인터 방식을 사용합니다.

• 팰린드롬의 중심: 팰린드롬은 항상 중심을 기준으로 양쪽이 대칭입니다. 중심이 될 수 있는 경우는 두 가지입니다.
  1. 중심이 하나의 문자인 경우 (홀수 길이 팰린드롬, 예: "aba"의 'b')
  2. 중심이 두 문자 사이인 경우 (짝수 길이 팰린드롬, 예: "abba"의 'bb' 사이)
• 양방향 탐색 (getPalin): 주어진 중심(l, r)에서 시작하여, 범위를 벗어나지 않고 양끝 문자가 같을 때까지 l은 왼쪽으로, r은 오른쪽으로 한 칸씩 확장합니다.
• 길이 계산: 확장이 멈춘 시점은 양끝 문자가 다르거나 범위를 벗어난 시점입니다. 따라서 직전까지 유효했던 팰린드롬의 길이는 (r - 1) - (l + 1) + 1, 즉 r - l - 1이 됩니다.

코드 2

class Solution {
    public int solution(String s) {
        int ans = 1;
        
        for (int i = 0; i < s.length() - 1; i++) {
            // 1. 홀수 길이 팰린드롬 (중심이 i인 경우)
            int len1 = getPalin(s, i, i);
            
            // 2. 짝수 길이 팰린드롬 (중심이 i와 i+1 사이인 경우)
            int len2 = getPalin(s, i, i + 1);
            
            // 더 긴 값을 현재까지의 최대 길이와 비교하여 갱신
            ans = Math.max(ans, Math.max(len1, len2));
        }
        
        return ans;
    }
    
    // 중심으로부터 양옆으로 확장하며 팰린드롬 길이를 구하는 메서드
    int getPalin(String s, int l, int r) {
        // 인덱스가 유효하고 양끝 문자가 같을 때까지 확장
        while (l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r)) {
            l--;
            r++;
        }
        
        // 반복문 종료 시점에서는 조건을 만족하지 않는 상태이므로
        // 유효했던 길이는 r - l - 1 이 됨
        return r - l - 1;
    }
}

알고리즘 분류

문자열 (String), 완전 탐색 (Brute Force), 투 포인터 (Two Pointers)