[프로그래머스] 가장 긴 팰린드롬 - PYTHON

문제보기

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

프로그래머스

 

 

풀이 & 코드

DP만 잘 찾을 수 있다면 할만한 문제. 물론 필자는 한번에 찾지 못해 빙빙 돌아가긴 했다. 사실 DP문제를 마주할 때마다 DP보다 다른 방법이 더 시간적으로 빠를 거 같다고 생각이 들 때가 많다. 결과적으로는 DP가 더 빠르지만 말이다. 이 문제도 그러했다. 최장길이의 팰린드롬을 찾는 이 문제는 길이가 긴 것부터 짧은 것까지 팰린드롬인지 확인하는 방법이 짧은 것부터 판단하며 길이를 늘려가는 DP보다 더 빠를 것 같다. 하지만 S의 길이가 10이나 15정도가 아니라 2500이고 팰린드롬의 길이가 매우 짧다면, 당연히 DP가 더 빠를 것이다. INPUT의 크기를 보는 것 또한 DP문제인지 판단하는 데 도움이 되는 기준인 것 같기도 하다. 물론 이렇게 눈치채는 게 정석은 아니지만 말이다!ㅎ

 

DP로 푸는 방법의 인사이트는 간단하다. 

dp[start+1][end-1] and s[start] == s[end]

s안에서 확인하고 싶은 문자열 s[start: end]라고 했을 때 이것이 팰린드롬인지 확인하려면 s[start+1: end-1] 이 팰린드롬이고 s[start] == s[end]이어야 한다. 즉 특정 문자열의 양 끝이 같고 그 안에의 문자열이 팰린드롬이면 해당 문자열을 팰린드롬이다! 따라서 특정 문자열의 길이가 1이거나, 2일때 dp에 저장해주고 3이상일 때부터 위의 인사이트를 활용해주면 된다.

 

def solution(s):
    n = len(s)
    dp = [[0 for _ in range(n+1)] for _ in range(n+1)]
    answer = 1
    
    # 길이가 1일 때
    for i in range(0, n):
        dp[i][i] = 1
        
    # 길이가 2일 때
    for i in range(0, n-1):
        if s[i] == s[i+1]:
            dp[i][i+1] = 1
            answer = 2

    # 길이가 3이상일 때
    for size in range(3,n+1):
        for start in range(0, n-size+1):
            end = start + size -1
            if dp[start+1][end-1] and s[start] == s[end]:
                dp[start][end] = 1
                answer = max(answer, size)
        
    return answer

 

 

후기

풀이 처음에 말했던 대로 DP를 활요하지 않고 코드를 작성하면 다음과 같다. 다른 분의 풀이가 필자가 짠 것보다 깔끔해서 주석만 추가해서 올린다. ([다른 사람의 풀이]에 있는 김현우 , -  님의 풀이입니다.) 길이가 긴것부터 길이를 줄여가며 팰린드롬인지 판단하고 팰린드롬이나오면 바로 return하는 함수이다.

def solution(s):
    if s == s[::-1] :
        return len(s)
    for i in range(1, len(s)) :
        n = len(s) - i
        indexList = [x for x in range(len(s) - n + 1)]
        # n: 판단할 문자열의 길이, indexList: 판단할 문자열의 시작점
        for e in indexList :
            # p: 판단할 문자열
            p = s[e: e + n]
            if p == p[::-1] :
                return len(p)
    return -1

 

DP활용제출, 일반 알고리즘활용 제출

전체적인 효율성을 타지만 일반 알고리즘을 활용한 것이 더 효과적으로 보이지만 특정 상황인 효율성 테스트 1을 비교해보면, DP를 활용하는 것이 효과적임을 알 수 있다.