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

DP 사용

class Solution {
	boolean[][] dp;
    
   	public int solution(String s) {
		int answer = 0;
		dp = new boolean[s.length()][s.length()];

		for(int i=0;i<s.length();i++){
			dp[i][i] = true; //단일 문자는 펠린드롬을 만족하는 조건이다.
			answer = 1;
		}
        
		for(int i=0;i<s.length()-1;i++){
		// 만약 'aa', 'bb'와 같이 동일한 문자가 연속해서 나오는 경우는 별도로 갱신해준다
			if(s.charAt(i)==s.charAt(i+1)) dp[i][i+1] = true;
		}

		for(int len = 3;len<=s.length();len++){
			for(int i=0;i+len<=s.length();i++){
				int j = i+len-1;
                
				if(s.charAt(i)==s.charAt(j) && dp[i+1][j-1]){
					dp[i][j] = true;
					answer = len;
				}
			}
		}

		return answer;
	}
}

 

첫번째 for문과 두번째 for문으로 각각 길이 1인 문자열과, 동일한 문자가 연속해서 나오는 길이 2의 문자열의 팰린드롬 처리는 완료 되었다.

 

이 이후부터 길이 3인 문자열부터 시작하여 문자열의 길이만큼 반복해 해당 길이의 문자열이 팰린드롬을 만족하는지 확인한다.