[프로그래머스(파이썬/Python)] 가장 긴 팰린드롬

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

코딩테스트 연습 - 가장 긴 팰린드롬

 

아래 코드에서 설명한 두 개의 주석이 핵심입니다.

 

1. 팰린드롬 문자열인지 확인할 때는 포인터 두 개를 두고(투 포인터) 왼쪽 끝과 오른쪽 끝이 일치하는지 확인하면 됩니다. left < right까지 문자열이 일치한다면 팰린드롬이죠(스터디를 하다가 str == str[::-1]로 팰린드롬을 확인할 수 있다는 걸 알고 자괴감이 들긴 했습니다).

 

2. 가장 긴 팰린드롬 문자열을 찾기 위해서는 가장 긴 문자열부터 탐색하면 됩니다. 가장 긴 문자열을 시도해보다가 팰린드롬이 맞다면 그보다 짧은 문자열에 대해서는 해보지 않아도 되기 때문이죠. 아마 이 부분에서 길이가 짧은 녀석들도 일일이 다 탐색한다면 시간초과가 뜰 수도(?) 있을 것 같네요.

 

[풀이]

def isPalidrome(str):
    # 왼쪽끝, 오른쪽에서부터 좁혀오면서 비교하기
    left, right = 0, len(str)-1
    while(left < right):
        if str[left] != str[right]:
            return False
        else:
            left += 1
            right -= 1
    return True

def solution(s):
    answer = 0
    # 가장 긴 문자열 길이부터 탐색하면서 팰린드롬이면 종료
    for length in range(len(s), 0, -1):
        for i in range(0, len(s) - length + 1):
            if isPalidrome(s[i:i+length]):
                return length

s = "a"
print(solution(s))