프로그래머스 - 가장 긴 팰린드롬(Java, 자바)

문제 링크

문제 설명

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

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

제한사항

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

---

입출력 예

s	answer
"abcdcba"	7
"abacde"	3

입출력 예 설명

입출력 예 #1

4번째자리 'd'를 기준으로 문자열 s 전체가 팰린드롬이 되므로 7을 return합니다.

입출력 예 #2

2번째자리 'b'를 기준으로 "aba"가 팰린드롬이 되므로 3을 return합니다.

---

문제 풀이 방법

이 문제를 풀면서 삼중 반복문을 사용하면 효율성에서 문제가 되지 않을까 하고 걱정부터 했던 문제였다.
하지만 삼중 반복문을 사용해도 효율성 테스트에서 문제가 되지 않았다.

삼중 반복문이 필요한 이유는 검토할 문자열의 길이 조절, 검토할 문자열의 시작 지점, 팰린드롬 여부 확인 이렇게 세가지를 판별 해야하기 때문에 삼중 반복문이 필요하다.

 

길이가 6일 때는 문자열의 길이와 동일 하므로 문자열 처음부터 검사를 한다.
하지만 여기서 팰린드롬이 나오지 않아 길이를 줄여서 다시 검사를 한다.

길이가 5일 때는 시작 지점이 2개가 된다. 하지만 여기서도 팰린드롬이 나오지 않아 길이를 다시 줄여서 확인을 해야한다.

길이가 4일 때는 시작 지점이 3개가 된다. 하지만 여기서도 팰린드롬이 나오지 않아 길이를 다시 줄여서 확인을 해야한다.

길이가 3일 때는 시작 지점이 4개가 된다.
하지만 첫번째부터 팰린드롬이 나오기 때문에 이 길이를 return 하면 된다.

팰린드롬을 검사 할때 문자열 길이의 2로 나눈 크기 만큼 하는 이유는 팰린드롬은 문자열 중심으로 왼쪽과 오른쪽을 비교하기 때문이다.

---

전체 코드

class Solution {
    public static char[] ch;
    public int solution(String s) {

        ch = s.toCharArray();

        ch = s.toCharArray();

        for (int len = s.length(); len > 1; len--) {

            for (int start = 0; start + len <= s.length(); start++) {
                if(isPalindrome(start, len)){
                    return len;
                }
            }
        }

        return 1;
    }

    public static boolean isPalindrome(int start, int len){

        for (int i = 0; i < len /2; i++) {
            if (ch[start + i] != ch[start + len - i - 1]) {
                return false;
            }
        }
        return true;
    }
}