[12904] 가장 긴 팰린드롬

✔ 가장 긴 팰린드롬

[프로그래머스 12904]

문제 분석하기

가장 긴 팰린드롬의 길이부터 탐색하며, 팰린드롬을 만족하는지 확인하도록 함

손으로 풀어보기

1. 가장 긴 문자열이 팰린드롬을 만족하는지 확인
2. 가장 긴 팰린드롬의 길이를 반환

슈도코드 작성하기

s(문자열)
for(size -> s의 길이부터 0까지) {
    for(start -> start + size가 s의 길이보다 작을 때까지) {
        if(팰린드롬이 맞는지(s, start, size)) {
            size 반환
        }
    }
}
1 반환

팰린드롬이 맞는지 {
    for(i -> size / 2만큼) {
        if(s의 start + i와 s의 start + size - i - 1이 다르다면)
            팰린드롬이 아니므로 false 반환
    }
    true 반환
}

코드 구현하기

/**
 * 12904) 가장_긴_팰린드롬
 */
public class L007_12904 {
    // s(문자열)
    public int solution(String s) {
        // size(가장 긴 팰린드롬의 길이)
        for (int size = s.length(); size > 0; size--) {
            // start(팰린드롬의 시작 위치 인덱스)
            for (int start = 0; start + size <= s.length(); start++) {
                // 팰린드롬이 맞다면
                if (isPalindrome(s, start, size)) {
                    // size 반환
                    return size;
                }
            }
        }
        // 가장 작은 팰린드롬의 길이인 1 반환
        return 1;
    }

    // 팰린드롬이 맞는지 함수
    private boolean isPalindrome(String s, int start, int size) {
        // size의 반절만큼 반복하며 앞과 뒤의 글자를 확인
        for (int i = 0; i < size / 2; i++) {
            // s의 start + i와 s의 start + size - i - 1이 다르다면
            if (s.charAt(start + i) != s.charAt(start + size - i - 1)) {
                // 팰린드롬이 아니므로 false 반환
                return false;
            }
        }
        // true 반환
        return true;
    }

    // 테스트 케이스
    public static void main(String[] args) {
        L007_12904 solution = new L007_12904();

        String s = "abcdcba";

        int result = solution.solution(s);

        System.out.println(result);
    }
}