Question

O(n) 풀이 - 마나커 알고리즘

핵심 아이디어는 펠린드롬의 대칭성을 이용하는 것입니다.

일단 짝수 펠린드롬의 길이를 고려하기 위해 문자열을 계산하기 편하게 변형하겠습니다.

예시

abaxabaxabb

문자열의 각 문자를 중심으로 했을 때의 최대 펠린드롬의 길이를 구하고 그 중 최댓값을 구할 겁니다.

a b a x a b a x a b b
1 3 1 7 1 9 1 5 1 1 1 // 각 문자를 중심으로 했을 때 최대 펠린드롬의 길이입니다.

다만 이렇게 하면 한가지 문제가 있는데 마지막 문자열 bb가 길이 2짜리인 펠린드롬이라는 것을 풀이과정에서 놓치게 됩니다.
따라서, 짝수 펠린드롬도 고려하기 위해 문자열을 변형시킬겁니다.

# a # b # a # x # a # b # a # x # a # b # b #

문자열 사이사이에 더미 문자열을 넣어주고 각 문자열의 최대 펠린드롬의 길이를 구해봅시다.

0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22
#	a	#	b	#	a	#	x	#	a	#	b	#	a	#	x	#	a	#	b	#	b	#
0	1	0	3	0	1	0	7	0	1	0	9	0	1	0	5	0	1	0	1	2	1	0

11번째 b를 중심으로 한 펠린드롬의 길이가 9이므로 가장 긴 것을 알 수 있습니다.
마나커 알고리즘으로 테이블을 완성시키고 그 중 최댓값을 구할겁니다.

마나커 알고리즘

이제 테이블을 채워봅시다. 이것도 일종의 DP니까 테이블이름은 DP라고 합시다.
DP[i]: i번째 문자를 중심으로 한 펠린드롬의 최대 길이

초기상태

0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22
#	a	#	b	#	a	#	x	#	a	#	b	#	a	#	x	#	a	#	b	#	b	#
-	-	-	-	-	-	-	-	-	-	-	-	-	-	-	-	-	-	-	-	-	-	-

0번째 #은 양 옆으로 펠린드롬을 확장할 수 없습니다. 따라서 DP[0]=0입니다.

0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22
#	a	#	b	#	a	#	x	#	a	#	b	#	a	#	x	#	a	#	b	#	b	#
0	-	-	-	-	-	-	-	-	-	-	-	-	-	-	-	-	-	-	-	-	-	-

1번째 a는 양옆으로 1칸 확장 가능합니다. 따라서 길이는 DP[0]=1입니다.

0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22
#	a	#	b	#	a	#	x	#	a	#	b	#	a	#	x	#	a	#	b	#	b	#
0	1	-	-	-	-	-	-	-	-	-	-	-	-	-	-	-	-	-	-	-	-	-

중간 설명을 생략하고 5번째 a를 계산하고 있다고 해봅시다. 다음과 같은 상황일 것입니다.

0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22
#	a	#	b	#	a	#	x	#	a	#	b	#	a	#	x	#	a	#	b	#	b	#
0	1	0	3	0	여기 구해야 함	-	-	-	-	-	-	-	-	-	-	-	-	-	-	-	-	-

이미 이전의 b가 양쪽으로 3만큼 확장할 수 있다는 걸 알고 있습니다. 지금 구하려는 a는 그 b의 오른쪽 날개 안에 포함되어있죠. 그 말은, b의 왼쪽날개에도 a가 존재한다는 것입니다.

0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22
#	a	#	b	#	a	#	x	#	a	#	b	#	a	#	x	#	a	#	b	#	b	#
0	1	0	3	0	1	-	-	-	-	-	-	-	-	-	-	-	-	-	-	-	-	-

1번 a는 양옆으로 1칸이 같은 문자이므로 5번 a도 양옆으로 1칸이 같은문자여야 합니다. 그럼 우린 (4번 #, 6번 #)의 비교를 생략하고 바로 (3번 b, 7번 x)의 비교를 하면 됩니다.

어찌저찌해서 11번째 b를 구하는 상황이라고 합시다. 테이블은 다음과 같이 채워져있을 겁니다.

0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22
#	a	#	b	#	a	#	x	#	a	#	b	#	a	#	x	#	a	#	b	#	b	#
0	1	0	3	0	1	0	7	0	1	0	여기 구해야함	-	-	-	-	-	-	-	-	-	-	-

11번째 b의 반대편은 3번째 b군요.

우린 3번째 b의 양 옆으로 3쌍의 문자가 같다는 정보를 알고 있습니다.
펠린드롬은 왼쪽 오른쪽의 모양이 같아야 하니 11번째 b도 양 옆으로 3쌍의 문자가 같아야겠군요.

C: 가장 큰 펠린드롬의 중심
R: 가장 큰 펠린드롬의 오른쪽 끝
L======C======R
#a#b#a#x#a#b#a#x#a#b#b#
  <--------^-------->

직접 세어보니 길이가 9네요.

사실, 왼쪽 날개의 쌍둥이가 갖는 값이 의미하는 건 최소길이입니다.

여태까지 우리는 최대 펠린드롬의 길이를 구할때,
현재위치에서 '바로 옆' 사이드부터 비교했습니다.

.. x # a # b # a # x..
b가 중심인 펠린드롬의 최대길이를 구하기 위해
양옆의 #부터 비교하기 시작한다.

왼쪽의 쌍둥이 b가 중심인 펠린드롬은 최대길이 3 이라는 걸 이미 구했으니까
현재 b의 양 옆으로 3칸까지는 문자들이 쌍을 이루는 게 보장됩니다. 즉, x부터 비교를 하면 된다는 거죠.

펠린드롬은 왼쪽, 오른쪽이 대칭이니까 왼쪽 b가 길이 3짜리 내부 펠린드롬의 중심이라면, 오른쪽 b를 중심으로 한 같은 모양의 내부 펠린드롬이 존재할 것입니다. 하지만 외부 펠린드롬 뒤에 문자가 더 있으니까 그 문자들이 현재 'b'(오른쪽 b)가 중심인 펠린드롬을 확장할 가능성도 있습니다.

그래서 왼쪽 b의 값인 DP[3]이 오른쪽 b가 중심인 펠린드롬의 최소길이가 됩니다.

단, 주의해야할 점이 있는데 DP[2*C - i]의 값이 R보다 클 수도 있다는 것입니다.
무슨 상황이냐 하면,

  L=========C=========R
b # x # b # a # b # x # y #
0 1 2 0 1 0 5 0 1 0 ? - - -
    ^               ^
  2*c-i             i

위의 두 x의 경우 입니다.
왼쪽 x의 값 2를 그대로 오른쪽에서 최소길이로 잡아버리면, 오른쪽 x에서 양옆으로 2칸 떨어진 b와 y가 이미 같다고 가정하고 비교를 시작하는 셈입니다.

이 경우에는 최소길이를 현재위치 ~ R까지 길이로 잡아야 합니다.

즉, 비교를 시작하는 최소길이는 min(DP[2*c - i], R-i)가 되겠네요.

정리

알고리즘 동작은 다음과 같습니다.

현재 위치에서 양 사이드가 같은지를 비교할 오프셋(최소길이)을 구한다.
오프셋만큼 떨어진 위치부터 최대로 문자가 같은 길이를 구함
현재 위치에서 가장 긴 펠린드롬의 끝이 이전 펠린드롬의 끝( R )보다 크면, R과 C를 업데이트

R과 C가 뭔지 설명하기가 좀 어려운데,
펠린드롬 오른쪽 끝이 제일 큰녀석의 중심이 C, 오른쪽 끝이 R 입니다.

오프셋만큼 떨어진 부분부터 비교를 하기 때문에 시간복잡도는 O(n) 입니다.

작성중인 코드―Solution.java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
import java.util.*;
import java.util.stream.*;

import static java.lang.System.*;

class Solution
{
    public int solution(String s)
    {
        int c = 0;
        int r = 0;

        String extended = extend(s);

        int[] LPS = new int[extended.length()];

        for(int i=0;i<LPS.length;i++){
            if(i<=r){
                LPS[i] = Math.min(LPS[2*c-i], r - i);
            }

            while(i - LPS[i] - 1 >= 0 && i + LPS[i] + 1 < extended.length() && 
                    extended.charAt(i - LPS[i] - 1) == extended.charAt(i + LPS[i] + 1)){
                LPS[i]++;
            }

            if(LPS[i] + i > r){
                r = LPS[i] + i;
                c = i;
            }
        }

        return Arrays.stream(LPS).max().orElse(0);
    }

    String extend(String s){
        StringBuilder sb = new StringBuilder("#");
        for(int i=0;i<s.length();i++){
            sb.append(s.charAt(i)).append("#");
        }
        return sb.toString();
    }
}

오 새로운 알고리즘 알고가네요~ 감사합니다!

gihyeon9892@gmail.com―2024.04.01 16:37

Jzakka

2024.3.10 22:37

O(n) 풀이 - 마나커 알고리즘

마나커 알고리즘

정리

작성중인 코드―Solution.java

gihyeon9892@gmail.com―2024.04.01 16:37

0 개의 답변

답변 쓰기

이 입력폼은 마크다운 문법을 지원합니다. 마크다운 가이드 를 참고하세요.