[programmers] 가장 긴 팰린드롬 - 연습문제

코딩 테스트 연습 

 

---

<가장 긴 팰린드롬>

문제 설명

 

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

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

 

 

문제 풀이

   - my solution

def solution(s):
    answer = 1 # 문자열 길이 1
    
    for i in range(len(s)-1): # 모든 경우의 수 - 문자열  
        for j in range(i,len(s)):
            temp=s[i:j+1] 
            if temp==temp[::-1]: # 팰린드롬 확인
                if answer<len(temp): # 가장 긴 길이 
                    answer=len(temp)
            
    return answer

 

 

1) 문자열 길이가 1일 때 answer=1

2) 2중 for문 통해 문자열의 모든 경우의 수 찾기

   - 팰린드롬(앞뒤를 뒤집어도 똑같은 문자열) 확인

   - 가장 긴 길이 찾기

---

생각🤔

 

처음에 문제를 풀었을 때 정확성에서 1문제 실패와 효율성에서 실패가 떴었다.

정확성에서의 실패의 이유로는 문자열의 길이가 1일 때 answer을 1로 바꾸지 않아서였다. 

처음에 조건을 생각했긴 했지만 코드를 고치는 과정에서 빼먹은 것이었다..!

 

효율성의 실패의 이유로는 팰린드롬을 확인하는 과정에서의 for문 사용 때문이었다.

for문을 사용하여 앞 뒤로 같은지 확인하는 방식으로 하니 시간 초과가 떴다.

단순하게 생각하면 팰린드롬은 앞뒤를 뒤집어도 똑같은 문자열로 그냥 문자열을 뒤집어 같은지 확인하면 되는 것이었다.

(소름)

 

Level 3인 문제였지만 연습문제라 그런지 생각보다 빨리 풀 수 있었다.

---

출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges