[파이썬 python] 프로그래머스 - 가장 긴 팰린드롬

• 가장 긴 팰린드롬

문제 설명

앞뒤를 뒤집어도 똑같은 문자열을 팰린드롬(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합니다.

 

 

---

def longest_palindrome(s, left, right):
    if right - left == 1:
        length = 0
    else:
        length = 1
        
    while left >= 0 and right < len(s):
        if s[left] == s[right]:
            left -= 1
            right += 1
            length += 2
        else:
            break
            
    return length


def solution(s):
    answer = 1
    
    if len(s) == 1 or s == s[::-1]:
        return len(s)
    
    for i in range(len(s)-1):
        answer = max(answer, longest_palindrome(s, i, i+1), longest_palindrome(s, i, i+2) )
        
    return answer

 

정확성  테스트
테스트 1 〉	통과 (0.02ms, 10.3MB)
테스트 2 〉	통과 (0.02ms, 10.2MB)
테스트 3 〉	통과 (0.15ms, 10.2MB)
테스트 4 〉	통과 (0.15ms, 10.2MB)
테스트 5 〉	통과 (0.18ms, 10.2MB)
테스트 6 〉	통과 (0.13ms, 10.2MB)
테스트 7 〉	통과 (0.12ms, 10.3MB)
테스트 8 〉	통과 (0.13ms, 10.2MB)
테스트 9 〉	통과 (0.40ms, 10.2MB)
테스트 10 〉	통과 (0.24ms, 10.2MB)
테스트 11 〉	통과 (0.66ms, 10.2MB)
테스트 12 〉	통과 (0.00ms, 10.3MB)
테스트 13 〉	통과 (0.13ms, 10.1MB)
테스트 14 〉	통과 (0.25ms, 10.2MB)
테스트 15 〉	통과 (0.26ms, 10.2MB)
테스트 16 〉	통과 (0.29ms, 10.2MB)
테스트 17 〉	통과 (0.00ms, 10.2MB)
테스트 18 〉	통과 (0.01ms, 10.3MB)
테스트 19 〉	통과 (0.11ms, 10.3MB)
테스트 20 〉	통과 (0.34ms, 10.2MB)
테스트 21 〉	통과 (0.38ms, 10.2MB)
효율성  테스트
테스트 1 〉	통과 (3.25ms, 10.3MB)
테스트 2 〉	통과 (290.94ms, 10.2MB)

 

후기

 가장 긴 팰린드롬 문제다! 투 포인터를 사용하여 풀 수 있다.

 

풀이

* 팰린드롬은 딱 2가지 케이스다. 첫 번쨰는 abba처럼 짝수 팰린드롬, 두 번째는 abcba 처럼 홀수 팰린드롬.

(1) 먼저 문자열 s의 처음부터 끝까지를 탐색한다. 팰린드롬인지 아닌지를 탐색할 첫 번째 시작점이다.

(2) 시작점으로부터 팰린드롬인지 아닌지를 탐색한다. 짝수형 팰린드롬에는 시작점(left), 시작점+1(right)을 넣어주며, 홀수형 팰린드롬에는 시작점(left), 시작점+2(right)를 넣어준다.

(3) 만약 left와 right가 같다면 일단은 팰린드롬이 맞다. left를 한 칸 왼쪽으로, right을 한 칸 오른쪽으로 이동시키고 현재 팰린드롬 길이에 += 2 해준다.  left와 right가 다르다면 이제 팰린드롬이 아니니까 멈추고, 지금까지 최장 팰린드롬 길이를 리턴.

(4) 리턴한 팰린드롬 길이 중에 가장 큰 것이 정답이다.