프로그래머스 - 가장 긴 팰린드롬(파이썬, LV3)

https://programmers.co.kr/learn/courses/30/lessons/12904?language=python3

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

해당 문제는 문자열 핸들링 문제로 접근하였다.

팰린드롬은 reverse를 해도 똑같은 문자열을 뜻하는데,  (예 aba, abba)

주어진 문자열 내에서 가장 긴 팰린드롬의 길이를 찾는 문제였다.

 

처음에는 특정 문자열을 기준으로 계속 앞뒤로 한칸씩 이동해서 같은 문자일 때만 카운트하면서 가장 긴 문자열을 찾기만 하면 될 줄 알았다. 인데 함정이 하나 있었다(이 함정을 찾는데 정말 많은 시간을 소모했다).

 

바로 abba 와 같이 짝수의 연속성 문자열이다.

해당 문자열은 첫 번째a를 기준으로 잡으면 앞 뒤가 "(공백) b" 가 되고

두 번째 b를 잡으면 "a b" 가 되고 세 번째 b도 "b a" 네번째 a도 "b (공백)" 가 되어 위의 로직으로 해결이 불가했다.

 

그래서 비효율적일 수도 있겠지만 연속된 문자열을 체크하는 로직을 추가했다(CASE 1)

그리고 원래 세웠던 로직(CASE 2)으로 총 두 개의 큰 로직을 통해 파싱하니 정답을 찾을 수 있엇다

 

def solution(s):
    answer = 1
    len_s = len(s)
    
    # 인덱스 i 문자열 s 길이 
    for i in range(len_s):

        # 변수처리
        cnt_1 = 0
        strt_i = i
        fnsh_i = i+1
        
        # CASE 1 연속된 문자열이 같다면
        # 팰린드롬일 동안 체크, 문자 열 전체 길이보다 커지면 안됨
        while(strt_i >= 0 and fnsh_i <= len_s-1 and s[strt_i] == s[fnsh_i]):
            cnt_1 +=2
            strt_i -= 1 # 범위 증가
            fnsh_i += 1 # 범위 증가
            
        # 변수처리            
        cnt_2 = 1
        strt_i = i-1
        fnsh_i = i+1
        
        # CASE 2 연속된 문자열 고려하지 않음
        # 팰린드롬일 동안 체크, 문자 열 전체 길이보다 커지면 안됨
        while(strt_i>=0 and fnsh_i <= len_s-1 and s[strt_i] == s[fnsh_i] ):
            cnt_2 += 2
            strt_i -= 1 # 범위 증가
            fnsh_i += 1 # 범위 증가

        # cnt가 answer 보다 크면 교체
        if max(cnt_1, cnt_2) > answer:
            answer = max(cnt_1, cnt_2) 

    return answer