문제

풀이

모든 부분문자열을 다 검사하면 $O(n^3)$이 되어 효율성 테스트를 통과할 수 없다(고 생각했는데 의외로 된다). 그래서 투포인터 느낌으로 접근해서 가운데에서 점차 늘려가며 최대 길이를 찾아보았다. 길이가 홀수일 수도 있고 짝수일 수도 있다는 점을 유의해야 한다. $O(n^2)$이기 때문에 두 번 각각 순회해도 시간초과는 발생하지 않았다.

코드

def solution(s):
    N = len(s)
    answer = 1
    for m in range(N):
        temp = 1
        l = r = m
        while l > 0 and r < N - 1:
            l -= 1
            r += 1
            if s[l] == s[r]:
                temp += 2
            else:
                break
        answer = max(answer, temp)
    for m in range(N - 1):
        if s[m] == s[m + 1]:
            temp = 2
            l = m
            r = m + 1
            while l > 0 and r < N - 1:
                l -= 1
                r += 1
                if s[l] == s[r]:
                    temp += 2
                else:
                    break
            answer = max(answer, temp)
    return answer

사족

다른 사람의 코드를 보니 재귀로 한 줄만에 풀어버린 사람도 있었고, DP로 푼 사람도 있었다.

def solution(s):
    return len(s) if s[::-1] == s else max(solution(s[:-1]), solution(s[1:]))

효율성은 최악이지만 굉장히 멋있다.

DP로 풀 경우 i부터 j까지 모든 문자열을 판별하지만 태뷸레이션으로 팰린드롬 성립 여부를 저장해두어 계산 횟수를 줄인다. 또한 팰린드롬은 성립하거나 아니거나 두 경우만 있으므로 boolean 값을 이용하면 시간을 조금 더 단축할 수 있다.

그리고 놀랍게도

def solution(s):
    for i in range(len(s),0,-1):
        for j in range(len(s)-i+1):
            if s[j:j+i] == s[j:j+i][::-1]:
                return i

이 코드가 3358.34ms로 효율성 테스트를 통과한다...