[프로그래머스] 가장 긴 팰린트롬 Java 풀이

이 글은 혼자 학습한 내용을 바탕으로 작성되었습니다.

틀리거나 잘못된 정보가 있을 수 있습니다.

댓글로 알려주시면 수정하도록 하겠습니다.

---

1. 문제

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

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

2. 입력

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

3. 예제

s	answer
"abcdcba"	7
"abacde"	3

4. 풀이

먼저 팰린트롬 문자열을 찾는 방법을 알아보도록 하겠습니다.

 

팰린트룸은 가운데 위치를 기준으로 앞과 뒤 글자로 나누어 두 글자가 같으면 팰린트룸이라고 할 수 있습니다.

 

이때 문자열의 길이가 짝수와 홀수가 서로 다르다고 생각할 수 있습니다. 하지만 가운데 위치까지 문자열을 비교하는 횟수는 짝수, 홀수 모두 동일하기에 상관이 없습니다.

 

그러므로 문자열의 가운데 위치를 찾고 해당 위치까지 앞쪽과 뒤쪽의 문자를 비교하면서 서로 같으면 팰린트룸일 가능 성이 있는 것이며 만약 다르다면 팰린트롬이 아니라는 것입니다.

 

문제에서 가장 긴 팰린트롬 문자열의 길이를 찾는 것이므로 전체 문자열에서 시작하여 1개 문자만 존재하는 문자 순으로 반복하여 점점 작은 문자열을 확인하면서 팰린트롬 문자열을 찾는 과정이 필요합니다.

 

팰린트롬을 찾는 방법은 위에서 알아보았으므로 이제 입력으로 받은 문자열을 전체 문자열부터 1개씩 작은 문자열로 분리하여 팰린트룸을 확인하는 과정을 설명하겠습니다.

 

맨 처음에는 가장 긴 문자열인 입력 문자열 그대로를 팰린트롬 확인을 진행합니다.

 

만약 입력 문자열이 팰린트롬이 아니라면 확인할 문자열 길이를 1개 줄인 문자열을 팰린트롬 확인을 진행합니다.

그런데 1개 줄인 길이 4의 문자열의 경우 총 2가지의 경우가 생기므로 2가지 문자열을 모두 확인합니다.

 

만약 4개의 문자열을 확인한 결과 2가지 경우 모두 팰린트롬이 아니라면 3개의 문자열을 확인합니다.

이때 확인할 문자열의 개수는 총 3가지가 됩니다.

 

위 과정을 반복하면서 팰린트롬을 찾으면 확인할 문자열 길이가 결국 정답이 되므로 해당 값을 반환하여 문제를 풀 수 있습니다.

5. 코드

전체 코드는 Git에 있습니다.

int strLength = s.length() - 1;

for (int l = strLength; l > -1; l--) {
	for (int start = 0; start + l <= strLength; start++) {
		boolean isPel = true;

		int front = si;
		int back = si + l;

		while(front < back){
			if(s.charAt(front) != s.charAt(back)){
				isPel = false;
				break;
			}

			front++;
			back--;
		}
		if(isPel)
			return l + 1;
	}
}

return -1;