프로그래머스 가장 긴 팰린드롬 자바 풀이

문제 풀이 시간 :

문제 요약

문자열 s(길이 2,500 이하, 소문자만) 이 주어짐
앞뒤가 같은 부분 문자열(팰린드롬) 중 가장 길이가 긴 것의 길이를 구해야 함
즉, s의 부분문자열 중에서 좌우 대칭이 되는 가장 긴 구간의 길이를 찾는 문제

문제 풀이

이 문제는 처음보고 푼 방식이 순차탐색이었다.

초기 코드

java

class Solution
{
    public int solution(String s)
    {
        int answer = 1;

        int len = s.length();
        
        // 팰린드롬이 홀수인 경우
        for(int i=1;i<len-1;i++){
            int j=0;
            while(i-j>=0 && i+j<len){
                if(s.charAt(i-j) != s.charAt(i+j)){
                    break;
                }    
                j++;
            }
            answer = Math.max(answer, 1+((j-1)*2));
        }
        
        //팰린드롬이 짝수인 경우
        for(int i=0;i<len-1;i++){
            int j=0;
            while(i-j>=0 && i+j+1<len){
                if(s.charAt(i-j) != s.charAt(i+j+1)){
                    break;
                }
                j++;
            }
            answer = Math.max(answer, j*2);
        }

        return answer;
    }
}

위의 코드는 팰린드롬이 홀수인 경우와 짝수인 경우로 나누어 계산하였다.

또한, 각 경우에 대해 순차적으로 모든 경우를 계산하고 있기 때문에

$O(N^2)$ 의 시간복잡도를 가지게 된다.

이 코드도 통과는 하지만 더 효율적인 방법이 있을 것 같다는 생각에 검색을 해보니 Manacher라는 알고리즘이 존재했다.

해당 알고리즘에 대한 설명은 블로그의 알고리즘 항목에 설명해두었다.

Manacher 알고리즘을 통해 아래와 같은 좀 더 효율적인 코드로 작성할 수 있었다.

최종 코드

java

import java.util.*;

class Solution
{
    public int solution(String s)
    {
        if(s.length()<=1){
            return s.length();
        }
        int answer = 0;
        int len = s.length();
        StringBuilder sb = new StringBuilder(len*2+3);

				//문자 처음, 끝, 사이 특수문자 추가
        sb.append("*");
        for(int i=0;i<len;i++){
            sb.append("#").append(s.charAt(i));
        }
        sb.append("#").append("@");
        
        char[] T = sb.toString().toCharArray();
        int tLen = T.length;
        
        int[] P = new int[tLen];
        int center = 0;
        int right = 0;

        for(int i=1;i<tLen-1;i++){
            int mirror = 2*center-i; // 현재 중심에 대한 대칭 인덱스
            
            // 이미 탐색된 범위 안이라면, 대칭 위치의 결과를 일부 복사
            if(i<right)
                P[i] = Math.min(right-i, P[mirror]);
            else
                P[i] = 0;
            
            // 좌우 확장
            while(T[i-1-P[i]] == T[i+1+P[i]])
                P[i]++;
            
            // right와 center 갱신
            if(i+P[i]>right){
                center = i;
                right = i+P[i];
            }
            
            // 최장 팰린드롬 길이 갱신
            answer = Math.max(answer, P[i]);
        }

        return answer;
    }
}

가장 긴 팰린드롬

문제 풀이 시간 :

문제 요약

문제 풀이

초기 코드

최종 코드

함께 읽으면 좋은 글

택배상자

롤케이크 자르기

할인 행사

숫자 변환하기