5. Longest Palindromic Substring ☆★★ (잘 풀리면, DP도 이해하자!)

5. Longest Palindromic Substring

 

내 처음 코드

class Solution:
    def longestPalindrome(self, s: str) -> str:
        # 가장 긴 연속 부분문자열 중 Palindrome(좌우 반대 동일)인 문자열
        l, r = 0, 0
        max_ln = 0
        for r in range(1, len(s)):
            strs = s[l:r+1]
            while strs == strs[::-1]:
                max_ln= max(max_ln, r-l+1)  
                l+=1
        return max_ln

 

좋아! 네가 지금 쓰고 있는 방식은
아이디어는 좋지만, 코드가 문제를 제대로 해결하지 못해.
(그리고 리턴값도 max_ln이 아니라 문자열을 리턴해야 해!)

하나하나 짚어줄게.

---

❌ 문제점 1:

l을 한쪽 방향으로만 계속 이동시키고 있어.

• palindrome을 찾을 때마다 l += 1 해서 다음 시작점을 밀어버림.
• 그래서 모든 시작점에서의 palindrome을 찾지 못해.

---

❌ 문제점 2:

return max_ln

• 문제는 **가장 긴 "문자열"**을 리턴해야 해.
• 너는 지금 **길이(int)**만 리턴하고 있어.

---

✨ 이 문제의 표준 정석 풀이 (중심 확장법)

핵심 아이디어:

• 문자 하나 또는 문자 두 개를 중심으로
• 양쪽으로 확장하면서 가장 긴 palindrome을 찾는다.

👉 중심을 잡고 양쪽으로 expand하는 방식!

---

🔥 깔끔한 정답 코드

class Solution:
    def longestPalindrome(self, s: str) -> str:
        res = ""
        
        def expand(l, r):
            while l >= 0 and r < len(s) and s[l] == s[r]:
                l -= 1
                r += 1
            return s[l+1:r]  # 마지막에 while 탈출했을 때는 틀어진 상태니까 l+1, r-1 사이가 정답

        for i in range(len(s)):
            # 홀수 길이
            tmp1 = expand(i, i)
            # 짝수 길이
            tmp2 = expand(i, i+1)
            
            # 더 긴거 고르기
            if len(tmp1) > len(res):
                res = tmp1
            if len(tmp2) > len(res):
                res = tmp2
        
        return res

 

expand 함수에서 s[l] == s[r] 일때만, 확장되기때문에, palindrome 이 보장됨

---

✅ 설명

방법	설명
expand(i, i)	홀수 길이 중심 확장 (ex: "aba")
expand(i, i+1)	짝수 길이 중심 확장 (ex: "abba")
더 긴 문자열을 res에 저장

---

✨ 최종 요약

• 모든 위치를 중심으로 확장!
• 홀수와 짝수 둘 다 고려해야 함.
• 가장 긴 substring을 업데이트하면서 찾는다.

✨ DP 방식 풀이 아이디어 (추가 점수)

• dp[i][j] = True 이면 → s[i:j+1]이 Palindrome 이란 뜻!
• 점화식:
  • s[i] == s[j] 이고
  • (j - i <= 2) 또는 dp[i+1][j-1] == True 이면, → dp[i][j] = True

👉 즉,

• 양 끝 문자가 같고,
• 가운데 문자열도 palindrome이면,
• 전체도 palindrome이야!

---

🔥 코드

class Solution:
    def longestPalindrome(self, s: str) -> str:
        n = len(s)
        if n <= 1:
            return s  # 한 글자 이하는 바로 리턴

        # dp[l][r]: s[l:r+1] 이 palindrome 이면 True
        dp = [[False] * n for _ in range(n)]

        start, max_len = 0, 1  # 가장 긴 palindrome 시작 index, 길이 초기화

        # 1. 길이가 1인 부분 문자열은 항상 palindrome
        for l in range(n):
            dp[l][l] = True  # 자기 자신은 무조건 palindrome

        # 2. 길이 2 이상 부분 문자열 확인
        for length in range(2, n+1):  # 부분 문자열 길이 2, 3, ..., n
            for l in range(n - length + 1):  # 시작 인덱스 l
                r = l + length - 1  # 끝 인덱스 r

                if s[l] == s[r]:  # 양 끝 문자가 같아야 palindrome 가능성 있음
                    if length == 2 or dp[l+1][r-1]:  
                        # 길이 2인 경우는 바로 확인 (ex: "aa")
                        # 길이 >2 이면, 안쪽 부분이 palindrome이어야 함
                        dp[l][r] = True

                        # 지금 찾은 palindrome이 더 길면 업데이트
                        if length > max_len:
                            start = l
                            max_len = length

        # 3. 가장 긴 palindrome 부분 문자열 리턴
        return s[start:start+max_len]

---

✅ 요약

dp[i][j]	s[i:j+1]이 palindrome인지 표시
핵심 조건	s[i] == s[j] 그리고 가운데도 palindrome이면 True
리턴값	가장 긴 palindrome substring

 

2. 🔥 테이블로 dp 채워서 설명

예시로 s = "babad" 로 해볼게! (n=5)

문자열

 0   1   2   3   4
 b   a   b   a   d

---

1. 처음에 dp[i][i] = True

• 한 글자짜리는 무조건 palindrome.

l/r	0	1	2	3	4
0	T
1		T
2			T
3				T
4					T

---

2. 길이 2부터 검사 (length=2)

• b a, a b, b a, a d 다 비교
• (adjacent 두 글자)

l/r	0	1	2	3	4
0	T	F
1		T	F
2			T	F
3				T	F
4					T

(두 글자 짜리 palindrome 없음.)

---

3. 길이 3 검사 (length=3)

• bab, aba, bad
• 가운데 한 글자(a or b)가 palindrome이니까, 양 끝만 같으면 된다.
• "bab": b == b ✅ 그리고 a는 이미 palindrome ✅
• "aba": a == a ✅ 그리고 b는 palindrome ✅

업데이트!

l/r	0	1	2	3	4
0	T	F	T
1		T	F	T
2			T	F
3				T	F
4					T

(bab, aba 둘 다 palindrome!)

---

4. 길이 4, 5 검사 (length=4, 5)

• "baba", "abad" → 둘 다 양 끝 다름 ❌
• "babad" → 양 끝 다름 ❌

길이 4 이상은 없음.

---

최종 결과

• bab (또는 aba) 가 가장 긴 palindrome.

✅ 리턴: "bab" 또는 "aba"

---

✨ 요약해서 다시 보여줄게

dp[l][r] 의미	s[l:r+1]이 palindrome이면 True
l~r 채우는 방법	길이 2부터 n까지 늘려가면서 검사
r 계산법	r = l + length - 1
업데이트 조건	s[l]==s[r] 그리고 (length==2 or 안쪽이 palindrome)

---

🔥 정리

• 바깥 루프는 길이를 키우고,
• 안쪽 루프는 왼쪽 포인터 l을 이동시켜 substring 검사.
• **dp[l][r]**를 채워나가면서 가장 긴 palindrome 찾기!

---

✨ 마무리 비교

중심 확장법	빠르고 코드 짧다 (O(N^2))
DP 방식	메모리 더 쓰지만, 전체 경로 저장 가능 (O(N^2))

면접에서는 보통 "중심 확장법"이 더 선호되고,
DP는 "추가로 설명해줄 수 있으면" 플러스 점수야! 😎