[java] 프로그래머스 - 가장 긴 팰린드롬

문제

프로그래머스-가장 긴 팰린드롬
주어진 문자열에서 가장 긴 길이의 팰린드롬을 찾고 그 길이를 구하는 문제

• 제한 사항
  문자열 s의 길이 : s.length() <= 2,500
  문자열 s 는 알파벳 소문자로만 구성

• 예시
• s = “abcdcba”
  문자열 s가 팰린드롬이므로 정답은 7이다
• s = “abacde”
  문자열 s에서 팰린드롬은 ‘aba’이므로 정답은 3이다

풀이

문자열 s의 길이가 2보다 작은 경우는 그대로 s의 길이를 리턴한다
문자열 s를 캐릭터 배열로 만들어서 0부터 s의 길이-answer 까지 팰린드롬인지 확인한다
0 ~ 10까지라고 할 때, [10,9,8,7,6, …]로 줄여가며 0부터 해당 길이까지 팰린드롬을 확인한다

• s.length() - answer를 하는 이유는
  가장 긴 문자열부터 팰린드롬을 확인했으므로, 더 작은 범위를 확인할 필요가 없기 때문이다

팰린드롬을 확인할 때 start의 글자와 end의 글자를 비교해서 같으면 반복문을 통해 내부또한 팰린드롬인지 확인한다
짝수 길이, 홀수 길이를 고려해야하므로 문자열 길이의 절반을 mid라는 변수에 저장 후 mid>0까지 while을 돌린다

소스코드

class Solution{
	static char[] c;

	public int solution(String s) {
		int answer = 1;
		if (s.length() < 2)
			return s.length();
		c = s.toCharArray();
		for (int i = 0; i < s.length() - answer; i++) {
			answer = Math.max(answer,countPalin(i, s.length()-1));
		}

		return answer;
	}

	private int countPalin(int start, int end) {
		for (int i = end; i > start; i--) {
			if (c[start] == c[i] && isPalin(start, i))
				return i - start + 1;
		}
		return 0;
	}

	private boolean isPalin(int start, int end) {
		int mid = (end - start + 1) / 2;
		while (mid > 0) {
			if (c[start] != c[end])
				return false;
			start++;
			end--;
			mid--;
		}
		return true;
	}
}