프로그래머스 3단계 : 가장 긴 팰린드롬 (Java 자바)

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

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

 

제한사항

• 문자열 s의 길이 : 2,500 이하의 자연수
• 문자열 s는 알파벳 소문자로만 구성

 

입출력 예

 

 

풀이

주어진 문자열 s에서 가장 긴 팰린드롬 부분 문자열의 길이를 찾는 문제입니다.

 

solution 메서드: 이 메서드는 주어진 문자열 s에서 가장 긴 팰린드롬 부분 문자열의 길이를 반환하는 함수입니다.

첫 번째 반복문 for (int i = s.length(); i > 0; i--): 문자열의 길이를 줄여가며 팰린드롬 부분 문자열을 찾기 위한 반복문입니다. i는 현재 검사 중인 부분 문자열의 길이를 나타냅니다. 길이가 전체 문자열의 길이부터 1까지 역순으로 검사합니다.

두 번째 반복문 for (int j = 0; j + i <= s.length(); j++): 현재 길이 i로 검사 중인 팰린드롬 부분 문자열의 시작 위치 j를 나타냅니다. j + i가 문자열 길이를 초과하지 않도록 주의합니다.

if (isPalindrome(s, j, j + i - 1)) return i;: 현재 검사 중인 부분 문자열이 팰린드롬인지 확인하고, 팰린드롬이라면 해당 길이 i를 반환합니다. 이 부분에서 팰린드롬 여부를 확인하는 isPalindrome 메서드를 호출합니다.

isPalindrome 메서드: 주어진 문자열 value에서 start부터 end까지의 부분 문자열이 팰린드롬인지 확인하는 메서드입니다. 이 메서드는 투 포인터 방식을 사용하여 부분 문자열을 확인합니다.

이 코드의 핵심 아이디어는 가능한 모든 부분 문자열을 검사하며 가장 긴 팰린드롬 부분 문자열을 찾는 것입니다.

 

class Solution {
    public int solution(String s) {
        
        for (int i = s.length(); i > 0; i--) {
            for (int j = 0; j + i <= s.length(); j++) {
                // isPalindrome 메서드를 사용하여 현재 검사 중인 부분 문자열이 팰린드롬인지 확인합니다.
                if (isPalindrome(s, j, j + i - 1)) {
                    return i; // 팰린드롬이면 해당 길이(i)를 반환하고 종료합니다.
                }
            }
        }

        return 0; // 팰린드롬 부분 문자열이 없으면 0을 반환합니다.
    }
    
    // 주어진 문자열 value에서 start부터 end까지의 부분 문자열이 팰린드롬인지 확인하는 메서드
    boolean isPalindrome(String value, int start, int end) {
        while (start <= end) {
            // 시작과 끝 부분의 문자를 비교하여 팰린드롬 여부를 확인합니다.
            if (value.charAt(start++) != value.charAt(end--)) {
                return false; // 문자가 다르면 팰린드롬이 아닙니다.
            }
        }
        return true; // 모든 문자가 같으면 팰린드롬입니다.
    }
}