오늘의 문제는 문자열 s가 주어졌을 때, 해당 문자열의 substring 중 가장 긴 Palindromic 문자열을 return하는 것이다. 여기서 Palindromic 문자열이란 앞에서부터 읽나 뒤에서부터 읽나 동일한 문자열을 뜻한다. 나는 단순 구현으로 접근하여, 직관적인 방법으로 풀이하였다. 덕분에 풀이는 금방하였으나 시간 복잡도가 O(N^2)으로 매우 높았다. 이에 다른 사람의 풀이를 소개한다.
Two pointer를 활용한 풀이 방법은 다음과 같다.
3개의 index를 설정한다. left, right, middle
middle의 range를 전체(0 ~ n-1)중에서 (1 ~ n-2)로 설정하며 순회한다.
2-2) 참고로 문자열의 길이가 odd일 때와 even일 때 left 값 및 right 값 설정 기준이 다르다.
left값과 right 값이 동일하면, left 값을 한칸 좌측으로, right 값을 한칸 우측으로 이동하여 값이 동일한지 확인한다. (expand 과정)
해당 값이 longest인지 판단하여 max_str 결과를 갱신한다.
오늘은 Palindromic 문자열을 찾는 알고리즘에 대해 공부하였다. 이 문제의 경우 Manacher's Algorithm이란 최적의 알고리즘으로 알려준 것이 존재하나, 이해하기가 다소 어려워 실제 문제 풀이에 활용하기 어려울 것이라 판단하였다. 완벽한 이해까지 계속 시간이 걸려 이번에는 넘어 갔으나, 만약 다음에 유사한 문제를 또 다시 마주하게 된다면 그 때는 반드시 이해하고 넘어가야겠다. 이제 꽤 꾸준히 알고리즘 연습을 하고 있구나 라고 생각하였는데, 아직도 모르는게 많은 것 같다.