TIL (240903)

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

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

 

🔥다시보기🔥

 

문제 풀이 과정 및 풀이 코드

• 글을 읽으면 알 수 있지만, 팰린드롬이란 앞으로 읽어도 뒤로 읽어도 같은 문자를 팰린드롬이라고 한다. racar, 12321와 같은 예시를 생각할 수 있다.
• 이 문제는 주어지는 문자열 s의 모든 부분 문자열 중에서 가장 긴 팰린드롬의 길이를 리턴하는 문제이다.

 

• 첫번째 접근 - 실패
  1. 브루트포스
  2. 시간복잡도 : O(N^3)
  3. 간단하게 설명하자면 문자열 s를 배열로 만들고, s를 reversed로 뒤집이서 두 배열이 같은지 비교했다.
  4. 틀린 이유 : O(N^2) 시간복잡도가 소요된다고 생각했지만, reversed 가 O(N)의 시간복잡도가 소요되어 효율성 테스트를 통과하지 못한다.

def solution(s) :
    answer = 0	
    for i in range(len(s)) :
     for j in range(i, len(s)) :
         arr = list(s[i:j+1])
         arr_reverse = list(reversed(arr))
         if arr == arr_reverse :
             answer = max(answer, len(arr))
    return answer

 

• 두번째 접근
  1. 홀수 짝수 팰린드롬
  2. 시간복잡도 : O(N^2)
  3. 위의 방법에서 어떻게 하면 시간을 줄일 수 있을지 고민했으나 방법이 떠오르지 않아 다른 코드를 참조했다.
  4. i 번째 문자를 기준으로 홀수일 때, 짝수일 때 펠린드롬을 찾아 최대값을 리턴한다. 이 코드는 쪼끔 이해하기 어려웠다. 하나하나 뜯어보며 이해하려고 노력했다.

def solution(s) :
     # 코드 참조 : 홀수 / 짝수일 때 경우를 나눠서 생각해본다.
     ans = ""
     
     # 길이가 1이거나, s가 이미 펠린드롬인 경우 문자열 길이 리턴
     if len(s) < 2 or list(s) == reversed(list(s)) :
         return len(s)
         
     def palindrome(left, right) :
         while 0 <= left and right <= len(s) and s[left] == s[right-1] :
             left -= 1
             right += 1
         return s[left+1:right-1]
        
     for i in range(len(s)-1) :
         # i번째 문자를 기준으로 홀수일때, 짝수일 때 긴 펠린드롬을 찾는다.
         ans = max( ans, palindrome(i, i+1), palindrome(i, i+2) , key=len)
     print(ans)
     return len(ans)

 

• 세번째 접근
  1. DP
  2. 시간복잡도 : O(N^2)
  3. DP를 위한 공식은 다음과 같다.
     1. dp[i][j] 는 i번째 인덱스부터 j번째 인덱스 까지의 문자열이 펠린드롬이라는 것을 의미한다. 여기서 아래와 같은 조건이 도출된다.
     2. dp[i][i] 는 true로 펠린드롬이다. (자기자신 문자열은 모두 펠린드롬이다.)
     3. s[i] 와 s[i+1]이 같다면 dp[i][i+1] 은 true로 펠린드롬이다. (ex. "aa", "bb", ... )
     4. s[i] 와 s[j]가 같은 문자열일 때, dp[i+1][j-1]이 true로 펠린드롬이라면, dp[i][j] 또한 true로 펠린드롬이다.

def solution(s):
    # DP[i][j] = i, j 가 동일할 때, 펠린드롬을 만족하는지 여부 (true/false)
    answer = 0
    dp = [[False] * len(s) for _ in range(len(s))]
    
    # DP[i][i] = true 각 문자의 자신은 펠린드롬을 만족한다. 'a','b'
    for i in range(len(s)) :
        dp[i][i] = True
        answer = 1
    
    # DP[i][i+1] 의 문자열이 펠린드롬인지 확인하여 dp를 갱신한다.
    for i in range(len(s)-1):
        if s[i] == s[i+1] :
            dp[i][i+1] = True
            answer += 1
            
    # 문자열 3인것부터 비교시작
    for length in range(3, len(s)+1) :
        # i는 비교할 첫번째 index부터 index+len-1까지 펠린드롬을 만족하는지 i+1과 j-1을 비교합니다.
        for i in range((len(s)+1)-length) :
            j = i+length-1
            # i+1,j-1이 팰린드롬인 경우 i,j 또한 팰린드롬을 만족한다.
            if s[i] == s[j] and dp[i+1][j-1] :
                dp[i][j] = True
                answer = length
    return answer

 

참고

문자열 s가 펠린드롬인지 아닌지 여부 판별하기

length = len(s)
for i in range(length//2) :
 	if s[i] != s[length-1-i] :
    	return False
 return True