[맛있는물회] <알고리즘> "가장 긴 팰린드롬 찾기"

가장 긴 팰린드롬 찾기

 

앞뒤를 뒤집어도 똑같은 문자열을 팰린드롬(Palindrome)이라고 한다.

 

문제는 이러하다. (출처 - programmers.co.kr/)

 

처음 봤을때 어떤 알고리즘을 써야하는지 1도 감이 안와서 그냥 무작정 해봤다. 

 

비교할 substring의 길이를 i로 잡고 쭉쭉 늘려가며 막 비교를 해보았다.

i를 짝수, 홀수로 나눠서 홀수만 먼저 구현해보았다.     

 

좀 멍청한 방법이지만 그냥 다 비교해봤다.

홀수는 내가 만든 테스트에서는 잘 구현되는 것 처럼 보였다. ㅎㅎㅎ 

그다음, 길이가 짝수일때를 구현하려고 하니깐, 너무 막막한거였다. 

그래서 다른 사람들의 풀이를 조금 도움받아서 풀어보려고 구글링을 조금 해봤다.ㅎㅎ

 

먼저 보통 팰린드롬 문제에서 사용하는 알고리즘은 

Manacher's algorithm 이다.

 

한번 정리를 해보겠다. (사실 아직도 이 알고리즘이 이해가 안가는 부분이다. )

 

 

manacher의 알고리즘은 시간복잡도가 O(n)이라는 점에서 좋다. 

 

위에서 내가 사용한 방법의 시간복잡도는 O(n^2)으로 보이는데 훨씬 좋은 방법이다.

 

(출처 - algospot)

 

이러한 알고리즘은 각 문자의 중심으로 하는 팰린드롬을 사용하기 때문에 String의 길이가 짝수인 경우는 확인이 불가능하다. 

하지만 각 글자 사이에 더미 문자를 끼워넣어서 'a#b#c#d#d#c#b#a' 꼴로 만들고 풀면 풀 수 있다.

(알고리즘에 대해 좀 이해가 안가는 부분이다. 더 알아 봐야겠다 ㅠㅠ)