[프로그래머스][level3] 가장 긴 팰린드롬 (Python)

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

프로그래머스

 

문제 설명

앞뒤를 뒤집어도 똑같은 문자열을 팰린드롬(palindrome)이라고 합니다.
문자열 s가 주어질 때, s의 부분문자열(Substring)중 가장 긴 팰린드롬의 길이를 return 하는 solution 함수를 완성해 주세요.

예를들면, 문자열 s가 "abcdcba"이면 7을 return하고 "abacde"이면 3을 return합니다.

 

제한사항

• 문자열 s의 길이 : 2,500 이하의 자연수
• 문자열 s는 알파벳 소문자로만 구성

---

 

 

입출력 예sanswer

"abcdcba"	7
"abacde"	3

입출력 예 설명

입출력 예 #1
4번째자리 'd'를 기준으로 문자열 s 전체가 팰린드롬이 되므로 7을 return합니다.

입출력 예 #2
2번째자리 'b'를 기준으로 "aba"가 팰린드롬이 되므로 3을 return합니다.

 

 

팰린드롬(회문)이란?

: 팰린드롬(회문)은 거꾸로 읽어도 원래 문자열과 동일하다.

• 각 회문은 중심이 되는 축을 갖는다. 회문의 길이가 n이라 할 때,
  1. n이 홀수일 경우, (n+1)/2번재 문자가 중심이 된다.
  2. n이 짝수일 경우, n/2와 n/2+1번째 문자가 중심이 된다.
• 회문의 앞뒤에 같은 문자를 붙이면 계속 회문이 된다.
  • 앞뒤에 같은 문자를 붙일 경우, 뒤집었을 때도 앞뒤에 같은 문자를 붙이게 되기 때문

 

 

 

예시

S = banana 일 때, A[i]: i번 문자를 중심으로 했을 때 최대 반지름

• A[0] = 0      banana
• A[1] = 0      banana
• A[2] = 1      banana
• A[3] = 2      banana
• A[4] = 1      banana
• A[5] = 0      banana

계산 방법

• 각 i에 대해 A[i]를 1씩 늘리며 탐색
  • A[i]를 0으로 초기화한 후,
  • S[ i-(A[i]+1)] 과 S[ i+(A[i] +1 )]이 같다면 A[i]를 1씩 늘려준다.
  • 두 문자가 달라지거나 문자열 끝에 도달할 때 까지 반복한다.

 

 

 

 

1) 이중 for문으로 풀기

def solution(s):
    answer = 0

    # 시작 위치 설정
    for i in range(len(s)):
        # 끝 위치 설정
        for j in range(i,len(s)):
            # i위치부터 j위치까지의 문자열
            substring = s[i: j+1]
            
            # 팰린드롬 검증
            if substring == substring[::-1]:
                answer = max(answer,len(substring))
                
    return answer

 

 

2) 투포인터 풀이

def solution(s):
    answer = 0

    def expand(i,j):
        while(i>=0 and j<len(s) and s[i] == s[j]):
            i-=1
            j+=1
        # 팰린드롬 길이 반환
        return j-i-1
            
            
    for i in range(len(s)):
        # expand(i,i)는 홀수 (중심 축이 한글자), expand(i,i+1)는 짝수 (중심 축이 두글자)
        answer = max(answer, expand(i,i), expand(i,i+1))
    return answer