[Algorithm] 팰린드롬 판별 알고리즘

 

회문이란 반대로 읽어도 원본과 같은 단어를 말한다.

3개의 for 문을 사용하여 모든 회문을 찾을 수 있지만, 이 경우 시간 복잡도가 O(N^3)이 되므로,

• 이미 반복한 부분인 하위 문제의 결과를 DP table에 저장하여 시간 복잡도를 줄이는 알고리즘
• 이 경우 2개의 for문을 이용하므로 O(N^2)의 시간 복잡도를 가지게 된다.

 

 

N = int(input())
nums = [*map(int, input().split())]
M = int(input())

dp = [[0] * (N) for _ in range(N)]
# 각 한 단어씩은 팰린드롬 이므로 True 체크
for i in range(1,N):
    dp[i][i] = True

# 11, 22와 같이 연속된 값인 경우 팰린드롬이므로 True
for j in range(1, N-1):
    if nums[j] == nums[j+1]:
        dp[j][j+1] = True

# k만큼씩 떨어진 단어 체크
# 이 때, 하위 단어에 회문이 존재한다면
# dp[l][u]를 True로 변경
for k in range(1, N-1):
    for l in range(1, N-k):
        u = k+l
        if nums[l] == nums[u] and dp[l+1][u-1]:
            dp[l][u] = True

 

[1,2,1,3,1,2,1]을 예로 들어보자.

 

1. 각 숫자의 경우 -> 1, 2, 1 각각은 팰린드롬이므로 dp테이블에 True로 변경
2. 예시에는 없지만 -> 11, 22, 33과 같은 경우에도 팰린드롬이므로 dp테이블에 True로 변경
3. 이후 2중 반복문을 돌려준다.
4. l번째 단어와 l에서 k번째 떨어진 단어가 같은지 체크해주는데
5. 하위 단어에 팰린드롬이 존재한다면 지금 단어도 팰린드롬이다.
6. 1, 2, 1의 경우 k = 2, l = 1 인 경우 시작지점에 1, 끝 지점이 1로 동일하고
7. 가운데 2가 회문으로 기록되어 있으므로, 1,2,1은 회문이다.