[Python] 프로그래머스 Lv3. 가장 긴 팰린드롬

문제

https://school.programmers.co.kr/learn/courses/30/lessons/12904

프로그래머스

문제 요약

문자열 "s"가 주어졌을 때, 문자열의 부분문자열 중에서 앞에서 읽으나 뒤에서 읽으나 똑같은 팰린드롬을 찾는다.
그중 가장 긴 팰린드롬의 길이를 return하면 된다.

---

풀이

처음에는 부분문자열을 하나씩 잘라서 뒤집은 값이 같은지 확인해야 하나...? 생각했는데 그러면 경우의 수가 너무 많아진다.

결국 팰린드롬은 가운데를 기준으로 양쪽 문자가 같은지 확인하면서 늘려가면 된다.

예를 들어
"abcba"라면 가운데에 있는 "c"를 기준으로
"b == b"
"a == a"
이런 식으로 양쪽으로 한 칸씩 넓혀가면서 확인하면 된다.

근데 여기서 하나 생각해야 하는 게 있다.
팰린드롬의 길이가 홀수일 수도 있고 짝수일 수도 있다는 것.

홀수인 경우에는
"abcba"
처럼 하나의 문자를 중심으로 확인하면 되지만,

짝수인 경우에는
"abba"
처럼 가운데에 있는 두 문자 사이를 중심으로 확인해야 한다.

때문에 각 index마다 expand(i, i)로 홀수 길이 팰린드롬을 확인하고, expand(i, i + 1)로 짝수 길이 팰린드롬을 확인하면 된다.

"expand()"에서는 왼쪽 "l"과 오른쪽 "r"의 문자가 같은 동안 계속 양쪽으로 확장한다.

while l >= 0 and r < n and s[l] == s[r]:
    l -= 1
    r += 1

반복문이 끝났다는 건 이미 한 번 범위를 벗어났거나 서로 다른 문자를 만났다는 뜻이다.

때문에 실제 팰린드롬의 길이는 r - l - 1이 된다.

그리고 모든 위치를 중심으로 확인하면서 가장 긴 값을 "answer"에 저장하면 끝!

def solution(s):
    n = len(s)

    def expand(l, r):
        while l >= 0 and r < n and s[l] == s[r]:
            l -= 1
            r += 1
        return r - l - 1

    answer = 0
    for i in range(n):
        answer = max(answer, expand(i, i), expand(i, i + 1))
    return answer

시간복잡도

각 문자를 한 번씩 중심으로 잡기 때문에 총 n번 확인한다.

그리고 하나의 중심에서 최악의 경우 문자열 끝까지 양쪽으로 확장할 수 있으니까 이것도 O(n).

때문에 전체 시간복잡도는 O(n²) 이다.
문자열 길이가 최대 2,500이기 때문에 이 방식으로 충분히 해결할 수 있다.

별도의 배열 같은 것도 만들지 않고 index만 이용해서 확인하기 때문에 공간복잡도는 O(1).

처음에는 모든 부분문자열을 만들어야 하나 싶었는데... 팰린드롬은 가운데에서부터 확인하면 된다는 것만 알면 생각보다 깔끔하게 풀리는 문제였다.