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

https://programmers.co.kr/learn/courses/30/lessons/12904

코딩테스트 연습 - 가장 긴 팰린드롬

class Solution {
		public int solution(String s) {
			int answer = 1;

			if (s.length() == 1)
				return 1;

			for (int i = 0; i < s.length(); i++) {
				char start = s.charAt(i);
				loop: for (int j = i + 1; j < s.length(); j++) {
					if (s.charAt(j) == start && answer <= j - i + 1) {
						int left = i;
						int right = j;
						while (left <= right) {
							if (s.charAt(left++) != s.charAt(right--))
								continue loop;
						}

						if (answer < j - i + 1)
							answer = j - i + 1;
					}
				}
			}
			return answer;
		}

	}

소요시간 :38분

 

팰린드롬이란 반으로 접었을 때 모든 문자가 겹치는 것이라고 생각하면 편합니다.

예를들어 aabb, aacbb 등과 같은 문자열들은 반으로 접었을 때 딱 맞아 떨어집니다.

 

완전탐색 + 가지치기를 이용해 풀었습니다.

 

바깥쪽  for문은 시작하는 위치를 정하기 위한 for문 입니다.

안쪽 for문은 바깥쪽포문에서 구한 시작 위치부터 문자열의 끝까지 순회하기 위한 for문입니다.

 

1. 팰린드롬이 되기 위해서는 맨 앞의 문자와 맨 마지막의 문자가 무조건 같아야 팰린드롬이 될 수 있습니다.
2. 또한 현재 answer보다 짧은 팰린드롬은 시도해볼 필요가 없습니다.
3. acsgfw" 와 같은 문자는 팰린드롬의 길이가 0이라고 생각할 수 있지만 각각의 문자열은 팰린드롬이 될 수 있기 때문에 팰린드롬의 길이는 1입니다.

 

이 3가지를 염두하고 팰린드롬을 구현한다면 쉽게 구현할 수 있을것이라 생각합니다.

 

아 그리고 팰린드롬을 구할 때 substring으로 잘라서 함수로 보내줬더니 시간초과가 났습니다. 그래서 저렇게 for문 안쪽에 while을 이용해서 팰린드롬인지 아닌지 바로 확인해주었습니다~

 

끝!