가장 긴 팰린드롬

 

새로운 마나커 알고리즘(Manacher Algorithm)에 대해 학습할 수 있었다.

직관적인 이해가 어려웠던 알고리즘.

 

---

 

 

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

프로그래머스

 

---

 

Problem

문제는 간단하다. 주어진 문자열 내에서 가장 긴 회문의 길이를 도출하는 문제.

회문(palindrome)은 중간 글자를 기점으로 양쪽이 똑같은 문자열을 말한다.

즉, 문자열이 "banana"로 주어진다면 b [ a n a n a ] = 5 를 도출하면 되는 셈.

 

 

주의할 점은 '짝수 개수 문자의 회문'과 '홀수 개수 문자'의 회문을 구분해야 되는 것이다. 

 

즉, "aba" 처럼 b를 중심으로 문자를 뻗어나가는 회문이 존재하는 반면,

"abba" 처럼 bb를 중심으로 문자를 뻗어나가는 회문 또한 존재하니

 

회문의 중점이 되는 문자를 홀수 개수로 볼 것인지, 짝수 개수로 볼 것인지에 대한 고민이 필요하다.

 
 
 

Idea

먼저 직관적인 아이디어로 모든 문자 기준 양쪽을 탐색해보는 방법이 있다.

 

 

예시로 그림과 같이 문자열의 모든 index를 순회하면서

양쪽으로 한 칸씩 이동하며 다른 문자가 나올 때까지 계속 진행하는 것이다.

 

 

단, 이 방법만을 활용한다면 앞서 설명했던 '짝수 개수 문자의 회문'을 검증하지 못하므로,

 

 

그림과 같이 특정 index와 index+1, 혹은 특정 index와 index-1 이 같은 문자인지 먼저 검증하고,

만약 같다면 앞선 방법처럼 양쪽으로 한 칸씩 이동하여 다른 문자가 나올 때까지 확인하는 방법을 추가해야 한다.

 

이 방법은 가장 간단하지만, 문자열의 길이가 길어질수록 지수적으로 속도가 증가하여 효율적인 방법이 아니다. 

이러한 문제를 해결할 '마나커 알고리즘'에 대해 알아보자.

 

 

 

Solution (Manacher's Algorithm)

글이 너무 길어져, 마나커 알고리즘의 원리와 구현 방식은 다른 포스트로 대체한다.

 

https://hyungjun-950912.tistory.com/219

마나커 알고리즘 (Manacher's Algorithm)

 

 

Code (이중 for문)

먼저 '마나커 알고리즘' 을 적용하지 않은, 단순 이중 for문으로 전체 탐색한 코드이다.

 

import java.util.*;
class Solution {
    public int solution(String s) {
        int answer = 1;

        for(int i=0; i<s.length(); i++) {
            
            int count = 0;
            while((i-count)>=0 && (i+count)<s.length()) {
                if(s.charAt(i-count) != s.charAt(i+count)) {
                    break;
                }
                
                count++;
            }
            answer = Math.max(answer, count*2-1);
            
            count = 0;
            while((i-count)>=0 && (i+count+1)<s.length()) {
                if(s.charAt(i-count) != s.charAt(i+count+1)) {
                    break;
                }
                
                count++;
            }
            answer = Math.max(answer, count*2);
        }

        return answer;
    }
}

 

 

이런 방법으론 절대 통과 안 시킬 줄 알았는데 의외로 돼서 놀랐다.

단 효율성 테스트 2번 같이 크고 긴 데이터의 경우 시간이 21ms정도나 걸린다.

 
 

Code (Manacher's Algorithm)

이제 '마나커 알고리즘' 을 적용한 코드로 효율성을 확인해보자.

 

import java.util.*;
class Solution {
    public int solution(String s) {
        
        // 짝수 개수의 회문을 판별하기 위해 문자열 양끝 및 문자 사이에 특수 문자 "#" 추가
        StringBuilder sb = new StringBuilder("#");
        for(int i=0; i<s.length(); i++) {
            sb.append(s.charAt(i)).append("#");
        }
        
        String manacherString = sb.toString();
        
        
        /* dp 배열에는 현재 index 중심으로 몇 칸동안 회문이 진행되는지 저장
           즉, dp[i] = i를 기준으로 몇 칸의 회문이 완성되는가 */
        /* 이때 "#"을 더한 문자열이므로 최종 답안에는 /2를 해줘야 될 것 같지만
           "#"을 더한 문자열의 회문 반지름 길이 == 원본 문자열의 회문 길이가 됨 */
        int[] dp = new int[manacherString.length()];
        
        
        // 순회하며 '여태까지 만난 가장 멀리까지 간 회문'의 가운데 index, 마지막 index
        int middleIndex = 0;
        int lastIndex = 0;
        
        for(int i=0; i<manacherString.length(); i++) {
            
            // i 번째 문자(현재)를 기준으로 반지름 몇 칸동안 회문이 진행되는지 저장할 변수
            int halfLength = 0;
            
            // 최소 보장 길이를 '중점 기준' or '현재 ~ lastIndex까지의 길이' 중 작은 값으로
            if(i <= lastIndex) {
                halfLength = Math.min(
                                    dp[middleIndex - (i - middleIndex)],
                                    lastIndex - i
                                 );
            }
            
            
            // 최소 보장 길이 이후의 문자가 같은지 회문 검사
            int left = i - halfLength - 1;
            int right = i + halfLength + 1;
            
            while(left >= 0 && right < manacherString.length()) {
                
                // 양쪽 문자가 같으면 진행, 아니면 break
                if(manacherString.charAt(left) == manacherString.charAt(right)) {
                    halfLength++;
                    left--;
                    right++;
                }else {
                    break;
                }
            }
            // dp[i]에 지금 index 기준 만들어진 회문 길이의 반지름을 저장
            dp[i] = halfLength;
            
            
            // 이전 '여태까지 만난 가장 멀리까지 간 회문'보다 현재의 lastIndex가 더 크면 값 변경
            if(i + halfLength > lastIndex) {
                middleIndex = i;
                lastIndex = i + halfLength;
            }
        }
        
        
        // "#"를 조합한 문자열 중 가장 큰 반지름의 값 == 원본 문자열에서 가장 긴 회문의 길이
        int answer = -1;
        for(int i=0; i<dp.length; i++) {
            answer = Math.max(answer, dp[i]);
        }
        
        return answer;
    }
}

 

 

엌ㅋ 오히려 무지성 이중 for문 보다도 시간이 더 걸렸다;

하지만 효율성 테스트 2번의 경우 이중 for문이 21ms가 걸린 것에 비해 2ms라는 10배 빠른 결과를 보여주며

데이터가 큰 상황일수록 좋은 효율성을 보인다는 것을 알 수 있었다.

 

 

End

새로운 알고리즘을 알게 되었다.

처음 문제를 읽고 나서 이거 무조건 dp다 생각했는데, dp에 대한 이해 부족인지 해결 알고리즘까지는 떠올리지 못했다.

dp 완벽 숙달은 물론, 새로운 알고리즘도 떠올릴 수 있을 때까지 열심히 해야겠다..