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

가장 긴 팰린드롬

프로그래머스

 

• 내 풀이
  • n=2500이라 O(N^2)도 가능
  • 두 포인터(i, j) 돌리면서 양 끝을 비교
    • 해당 부분 문자열 전체를 뒤집어서 같은지 확인
    • s[i:j+1] == s[i:j+1][::-1]

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

    for i in range(n):
        for j in range(n-1, i-1, -1):
            if s[i] == s[j]:
                if s[i:j+1] == s[i:j+1][::-1]:
                    answer = max(answer, j - i + 1)
                    break

    return answer

 

 

• 다른 사람 풀이
  • DP 풀이 방식 → 시간 단축!!
  • 한번 확인한것은 확인 하지 않음

dp[i][j] = s[i] ~ s[j] 가 팰린드롬이면 True
1글자는 무조건 팰린드롬
2글자는 같으면 팰린드롬
3글자 이상은: 양 끝이 같고 안쪽(i+1 ~ j-1)이 팰린드롬이면 된다

한 글자들은 dp[i][i] = True
두 글자들은 s[i] == s[i+1] 이면 dp[i][i+1] = True
세 글자 이상은 s[i] == s[j] 그리고 dp[i+1][j-1] == True면 dp[i][j] = True

def solution(s):
    n = len(s)
    answer = 1  # 최소 한 글자는 팰린드롬
    dp = [[False] * n for _ in range(n)]
	
    # 한 글자 짜리는 팰린드롬
    for i in range(n):
        dp[i][i] = True

    for i in range(n-1):
        if s[i] == s[i+1]:
            dp[i][i+1] = True
            answer = 2

	# 3글자 이상
    for length in range(3, n+1):
        for i in range(n - length + 1):
            j = i + length - 1 # 끝 인덱스
            if s[i] == s[j] and dp[i+1][j-1]: # 양 끝 같고, 안쪽도 팰린드롬이면
                dp[i][j] = True
                answer = max(answer, length)

    return answer