[프로그래머스/3단계/자바] 가장 긴 팰린드롬 (정확성 O, 효율성 O)

가장 긴 팰린드롬

https://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는 알파벳 소문자로만 구성

풀이

앞으로 읽으나 뒤에서 읽으나 똑같은 단어를 우리나라에선 '회문(回文)'이라고 부르고, 영어에는 '팰린드롬(palindrome)'이라고 합니다.

이 문제는 해당 문자열에 팰린드롬이 있는지 찾아서, 그 중 가장 긴 팰린드롬의 길이를 반환해야 합니다.

 

저는 이 문제를 팰린드롬이 해당 문자열에서 가장 긴 경우(해당 문자열 그 자체인 경우)부터 가장 짧은 경우까지 하나하나 확인하면서, 만약 팰린드롬인 경우 해당 길이를 반환하도록 코드를 작성했습니다.

코드

class Solution
{
    public int solution(String s)
    {
        char[] chr = s.toCharArray();
        
        // 가장 긴 문자열부터 팰린드롬 검사
        for (int leng = s.length(); leng > 1; leng--) {
            
            // 시작 인덱스
            for (int start = 0; start + leng <= s.length(); start++) {
                boolean chk = true;
                
                // 처음부터 문자열 길이의 반틈만큼 문자가 같은지 비교
                for (int i = 0; i < leng/2; i++) {
                    if (chr[start + i] != chr[start + leng  - i - 1]) {
                        chk = false;
                        break;
                    }
                }
                
                if (chk) return leng;
            }
        }
        
        return 1;
    }
}

채점 결과