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

구현 문제입니다.

가장 긴 부분 문자열 부터 시작하여 모든 부분 문자열을 확인해 팰린드롬을 찾으면 됩니다.

처음에 두 개의 반복문 안에 subString으로 문자열을 짜르고 비교하는 코드를 사용했었습니다.

String le = str1.subString(0, di);
String ri = str1.subString(di+1, n);

StringBuilder sb = new StringBuilder(ri);
if(le.equals(sb.reverse().toString())){
    ...
}

 

예시 코드가 길어지기 때문에 생략했지만, 최소 subString이 네 개는 필요했습니다.

subString의 경우 O(N)의 시간이 소요되기 때문에 시간초과가 발생했습니다.

 

이후 방법은 subString이 아닌 반복문을 추가하되, 위치의 값으로 문자를 비교했습니다.

특정 위치에서 좌우를 비교하기 때문에 추가되는 반복문의 범위는 N/2입니다.

 

[구현 코드]

class Solution {
    public static int solution(String s) {

        char[] chars = s.toCharArray();
        int n = s.length();
        
        // 부분 문자열 길이
        for (int i = n-1; i>=1; i--) {
            // 부분 문자열이 시작하는 위치
            Par : for(int j=0; j+i<n; j++){
                // 좌우 비교
                for(int k=0; k<=i/2; k++){
                    if(!(i+j-k>=0 && i+j-k<n && j+k>=0 && j+k<n)) continue;
                    if(chars[j+k] != chars[i+j-k]) continue Par;
                }
                return i+1;
            }
        }

        return 1;
    }
}