Level 3 가장 긴 팰린드롬 Python 3

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

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

 

최종 코드

• GitHub -> https://github.com/hwayeon351/Programmers-Algorithms/blob/main/level3_가장긴팰린드롬.py

GitHub - hwayeon351/Programmers-Algorithms: 프로그래머스 알고리즘 소스 코드 모음

def solution(s):
    answer = 0
    for i in range(len(s)):
        for j in range(len(s), i, -1):
            new_s = s[i:j]
            if new_s == new_s[::-1]:
                answer = max(answer, len(new_s))
    return answer

---

풀이 과정

문자열의 시작 인덱스와 끝 인덱스를 조정하여 생긴 새로운 문자열을 앞뒤로 뒤집어도 똑같은지 판별해 가장 긴 팰린드롬을 찾아가면 된다.

def solution(s):
    answer = 0
    #i = 문자열의 시작 인덱스
    for i in range(len(s)):
    	#j = 문자열의 끝 인덱스
        for j in range(len(s), i, -1):
        	#i부터 j까지의 문자열 생성
            new_s = s[i:j]
            #뒤집었을 때에도 같으면 팰린드롬
            if new_s == new_s[::-1]:
            	#answer 값 갱신
                answer = max(answer, len(new_s))
    return answer

---

이전 풀이

풀이 시간 1시간 30분

문자열의 첫번째 인덱스부터 마지막 인덱스까지 팰린드롬인지 판별하고 아니라면 시작 인덱스와 끝 인덱스를 하나씩 조정해주는 방식으로 재귀 호출을 통해 문제를 풀었다.

import sys
sys.setrecursionlimit(7000000)
def palindrome(left, right, s, visit):
    global answer
    
    #visit[left][right]를 체크해줌으로써 중복 문자열 탐색을 방지한다
    if visit[left][right] == 1: return
    visit[left][right] = 1
    
    l, r = left, right
    #팰린드롬이라면 ck = True, 필린드롬이 아니라면 ck = False
    ck = True
    
	#팰린드롬인지 판별하기
    while l<=r:
    	#왼쪽 문자열과 오른쪽 문자열이 다른 경우, 팰린드롬 문자열이 아니다
        if s[l] != s[r]:
        	#left값을 오른쪽으로 한 칸 옮겨서 탐색
            if left+1 <= right: palindrome(left+1, right, s, visit)
            #right값을 왼쪽으로 한 칸 옮겨서 탐색
            if right-1 >= left: palindrome(left, right-1, s, visit)
            #팰린드롬이 아니므로 ck = False하고 while문을 나간다
            ck = False
            break
        #l은 오른쪽으로 한 칸, r은 왼쪽으로 한 칸 조정
        l+=1
        r-=1
    #팰린드롬이라면 해당 문자열의 길이와 answer을 비교하여 갱신
    if ck == True:
        cnt = right-left+1
        if answer < cnt: answer = cnt
            
def solution(s):
    global answer
    answer = 1
    visit = [[0]*len(s) for i in range(len(s))]
    palindrome(0, len(s)-1, s, visit)

    return answer