[프로그래머스/JAVA] Lv.3 - 가장 긴 팰린드롬

프로그래머스 Lv.3 - 가장 긴 팰린드롬

요구사항

• 주어진 문자열에서 가장 긴 팰린드롬 부분 문자열의 길이를 구하는 문제
• 팰린드롬: 앞뒤로 읽어도 동일한 문자열 (예: "abcba", "abba")

접근 방식

처음에 이분탐색으로 접근했으나 논리가 맞지 않아 투포인터(중심 확장법) 으로 구현했다.

핵심 아이디어

모든 위치 i를 팰린드롬의 중심으로 잡고 양쪽으로 확장하며 체크한다.
두 가지 경우를 따로 처리해야 한다.

• 홀수 길이: "abcba" → 중심이 한 글자 (lt = i-1, rt = i+1)
• 짝수 길이: "abba" → 중심이 두 글자 사이 (lt = i, rt = i+1)

주의사항

• 단일 문자도 팰린드롬이므로 홀수 경우 기본값은 1
• 마지막 문자도 중심이 될 수 있으므로 i < size 까지 순회

코드

import java.util.*;

class Solution {
    public int solution(String s) {
        int answer = 0;
        int size = s.length();

        for (int i = 0; i < size; i++) {
            // 홀수 길이
            int lt1 = i - 1, rt1 = i + 1;
            boolean success1 = false;
            while (check(lt1, rt1, size)) {
                if (s.charAt(lt1) == s.charAt(rt1)) {
                    lt1--; rt1++; success1 = true;
                } else break;
            }
            int result1 = success1 ? (rt1 - 1) - (lt1 + 1) + 1 : 1;

            // 짝수 길이
            int lt2 = i, rt2 = i + 1;
            boolean success2 = false;
            while (check(lt2, rt2, size)) {
                if (s.charAt(lt2) == s.charAt(rt2)) {
                    lt2--; rt2++; success2 = true;
                } else break;
            }
            int result2 = success2 ? (rt2 - 1) - (lt2 + 1) + 1 : 0;

            answer = Math.max(answer, Math.max(result1, result2));
        }
        return answer;
    }

    public boolean check(int lt, int rt, int n) {
        if (lt < 0 || rt >= n) return false;
        return true;
    }
}

느낀점

• 처음 직관은 투포인터가 맞았는데 이분탐색으로 풀려다가 시간을 많이 낭비했다.
• 문제를 보고 떠오르는 첫 직관을 너무 쉽게 버리지 말자.
• 홀수/짝수 팰린드롬을 따로 처리해야 한다는 점을 놓치지 말자.