프로그래머스 - [LEVEL 3] 가장 긴 팰린드롬

문제링크: https://programmers.co.kr/learn/courses/30/lessons/12904

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

---

문제 설명

- 팰린드롬 = 앞뒤를 뒤집어도 똑같은 문자열

- 문자열 s가 주어졌을 때 가장 긴 팰린드롬을 출력

- ex)

abcdcba	7	4번째 'd' 기준
abacde	3	2번째 'b' 기준

 

---

풀이

전부다 검사하면 되는 문제입니다. 효율성을 통과하지 못해 좋은 코드를 찾아 수정하여 제출하였습니다.

- 기준점을 잡아 홀수인 경우, 짝수인 경우 나누어 팰린드롬 검사

- 나머지는 주석 참조하시면 될 것 같습니다!

def palindrome(s, left, right):
    # 팰린드롬이 나올 수 있는 경우의 수 3가지
    # aba: 홀수
    # abba: 짝수
    # aaa: 홀수이지만 같음
    
    # 왼쪽 오른쪽이 같을 경우 계속 진행
    while 0 <= left and right <= len(s) and s[left] == s[right-1]:
        left -= 1
        right += 1
    return s[left+1:right-1]

def solution(s):
    
    # 길이가 1이거나 문자 전체가 팰린드롬 일경우 연산 x
    if len(s) < 2 or s == s[::-1]:
        return len(s)
    
    
    result = ""
    # i가 기준점이다.
    for i in range(len(s)-1):
        
        # print(i, palindrome(s, i, i+1), palindrome(s, i, i+2))
        
        # 길이 기준으로 result update
        # 홀수 / 짝수 두가지로 진행된다.
        result = max(result, palindrome(s, i, i+1), palindrome(s, i, i+2), key = len)
    
    return len(result)

 

이해가 어려우신분을 통해 짝수인 경우 홀수인 경우를 출력해 보았습니다.

1.  짝수: 'abccbaz' 같은 경우는 'abccba' 6글자를 찾아야 합니다.

    3번째글자 c일때 기준으로 짝수로 가장 긴 팰린드롬을 찾고 나머지는 팰린드롬이 형성되지 않아 한글자만 리턴합니다. 

 

2.  홀수: 'ababaz' 같은 경우는 'ababa' 5글자를 찾아야 합니다.

   3번째 글자 a일때 기준으로 홀수로 가장 긴팰린드롬을 찾고 나머지도 팰린드롬을 찾고 있으나 가장 길지 않으므로 패스합니다.

 

테스트 케이스 출력

 

코드: 깃헙 링크

출처 : 블로그 링크