[Programmers] 가장 긴 팰린드롬

알고리즘/programmers

꾸준함. 2022. 6. 21. 08:36

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

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

programmers.co.kr

세 단계로 나누어서 접근해야 하는 문제였습니다.

1. 모든 구간에 대해 길이가 1인 팰린드롬 존재하므로 모두 cache[i][i] 모두 1로 표시

2. 길이가 2인 팰린드롬 찾아 존재하면 answer를 2로 업데이트

3. 길이가 3 이상인 팰린드롬을 찾아 answer를 해당 길이로 업데이트

문자열 길이가 최대 2,500이므로 단순 브루트포스로 접근하면 안 되고 dp로 접근해야 효율성 체크도 통과합니다!

개발환경: Programmers IDE

지적, 조언, 질문 환영합니다! 질문 남겨주세요~

꾸준함