[2024 알고리즘 특강] 가장 긴 팰린드롬 - 프로그래머스 (파이썬)

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

프로그래머스

 

---

문제

앞뒤를 뒤집어도 똑같은 문자열을 팰린드롬(palindrome)이라고 합니다.
문자열 s가 주어질 때, s의 부분문자열(Substring)중 가장 긴 팰린드롬의 길이를 return 하는 solution 함수를 완성해 주세요.

예를들면, 문자열 s가 "abcdcba"이면 7을 return하고 "abacde"이면 3을 return합니다.

제한사항
- 문자열 s의 길이 : 2,500 이하의 자연수 
- 문자열 s는 알파벳 소문자로만 구성

입력

s	answer
"abcdcba"	7
"abacde"	3

입출력 예 #1

4번째자리 'd'를 기준으로 문자열 s 전체가 팰린드롬이 되므로 7을 return합니다.

 

입출력 예 #2

2번째자리 'b'를 기준으로 "aba"가 팰린드롬이 되므로 3을 return합니다.

 

우선 프로그래머스의 코드 형식은 입력 값을 따로 안 받아도 되고, 출력도 따로 안해도 된다.

 

그리고 이 문제 풀기 전에 회문 문제를 풀었어 가지고 기존 코드를 활용하면 될 것 같다는 생각이 들었지만,

기존은 단순히 단어를 뒤집어도 둘이 같으면 true 아니면 false를 출력하는 건데, 이번 문제는 false여도 안에 조금이라도 회문이 있다면 그 길이를 출력하는거기 때문에,,,어려웠다.

 

찾은 정답 코드와 이전 회문 문제 코드를 비교해봤다

근데 개인적으로 for j range(len(s), i, -1) 저 부분은 직관적이지 않아서 

for j in range(i+1, len(s)+1):

이렇게 바꿔도 실행이 잘 된다.

 

그래서 1차 코드는 아래와 같다.

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

 

하 지 만 !

다른 사람들이 올린 코드를 보다가 발견했는데 이게 가능한 줄 몰랐다.

슬라이싱과 역순을 한 번에 쓸 수 있다는 것을 처음 알게 되었다.

그리고 answer를 0이 아니라 1로 초기화 하는 것도, 어차피 없어도 최소한 1이 나오기 때문에 굳이 0으로 안해되는구나를 깨달으면서,,,아직 갈길이 멀다고 느껴지지만 조급하지 않게 차근차근 하면 언젠간,,,도달하거라고 믿는다ㅎ

def solution(s):
    answer = 1                     

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