[Swift] 프로그래머스 가장 긴 팰린드롬: Manacher Algorithm

프로그래머스

문제

앞뒤를 뒤집어도 똑같은 문자열을 Palindrome

주어진 문자열 s의 부분문자열 중 가장 긴 팰린드롬의 길이를 반환

제한사항

문자열 s의 길이는 2,500 이하의 자연수

풀이

DP로 풀어볼 수도 있다. 시간 복잡도를 줄여줄 수 있는 Manachar Algorithm으로 풀어보려고 한다.

Manacher Algorithm

각 문자를 중심으로 좌, 우 문자를 비교한다.

dbcbabcbabc 라는 문자열을 예시로 들면 그림과 같이 팰린드롬을 만드는 부분문자열이 존재한다.

문자열 내 팰린드롬들

부분 문자열의 반지름

 

순차적으로 탐색을 진행한다.

팰린드롬은 부분문자열 bcbabcb를 보면 a를 기준(거울과 같이)으로 대칭이 된다.

우측에 있는 원소 c는 대칭을 하되 이어지는 문자열로 인해서 더 큰 팰린드롬을 만들 수 있게 된다.

 

좀 더 자세히 설명해보자. 필요한 변수는 아래와 같다.

• 문자열을 순차적으로 탐색하는 index
• 각 index의 팰린드롬 길이를 가지는 배열 Palindromes
• 이전 index에서 다음 index에 영향을 미치는 팰린드롬의 반지름 radius
• 영향을 미치는 radius의 중점 center

 

radius와 center을 이해하는 것이 중요하다.

b를 가르키는 index에 왔을 때, radius와 center는 아래와 같이 지정되어 있을 것이다.

radius는 center + radius의 값을 표현한 것이다.

 

사용되는 변수들

 

다음으로 넘어가서 c를 가르키는 index가 되면, r보다 작다.

r보다 i가 작다는 것은 영향을 받기 때문에 거울과 같은 효과로 대칭이 되는 3번째 c와 동일한 팰린드롬의 길이가 기본값이다.

더 길어질 수도 있기 때문에 다음 양쪽 문자를 확인한다.

 

 

 

하지만 여기서 중요한 부분은 기본값으로 할 수 있는 방법은 총 3가지가 있다.

1. 팰린드롬 내에서 완벽한 대칭을 이루는 경우
2. 팰린드롬 내에서 위 그림과 같이 우측이 대칭점보다 긴 팰린드롬의 길이를 가지는 경우
3. 팰린드롬 내에서 좌측이 대칭점보다 긴 팰린드롬의 길이를 가지는 경우

1번과 2번의 기본값은 2 * center - index 이고 3번은 r - i 이다.

기본값이 왜 이렇게 나왔는지 이해하는데 조금 걸렸다.

 

 

1번과 2번의 기본값을 구해보자.

? 를 표현하기 위해서는 center와 index로 표현하려면 center - (index - center) 이다.

이것을 합치게 되면 2 * center - index 라는 값을 도출할 수 있다.

 

그리고 3번의 기본값을 구해보자.

위에 있는 그림과 반대로 좌측의 팰린드롬 길이가 길다면 영향을 받는 radius를 넘어간다는 말이다.

radius - index 로 기본값으로 시작할 수 있다.

 

그림을 그리면 쉽게 이해할 수 있다.

기본값이 정해졌으니 다음 위치의 문자들을 비교하면서 Palindromes[index]을 늘려주면 된다.

 

여기에서 문제가 발생한다. 가장 긴 팰린드롬의 길이가 짝수라면 위 방법으로 해결할 수 없다.

짝수를 해결하기 위해 a#b#c#c#b#a 와 같이 중간에 #이라는 기호를 넣어주면서 확인하면 된다.

 

이걸 토대로 구현해보자.

코드

import Foundation

func solution(_ s:String) -> Int {
    let string = s.reduce("#") { $0 + "\($1)#" }.map { $0 }
    var Palindromes = Array(repeating: 0, count: string.count)
    var center = 0, radius = 0, answer = 0

    for index in 0..<string.count {
        if radius >= index {
            Palindromes[index] = min(radius - index, Palindromes[2 * center - index])
        }

        while
            index - Palindromes[index] > 0,
            index + Palindromes[index] + 1 < string.count,
            string[index - Palindromes[index] - 1] == string[index + Palindromes[index] + 1] {
            Palindromes[index] += 1
        }

        if radius < index + Palindromes[index] {
            radius = index + Palindromes[index]
            center = index
        }

        answer = max(answer, Palindromes[index])
    }

    return answer
}​

 

Reference

• 참고 블로그
• Wikipedia