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

가장 긴 팰린드롬 : https://school.programmers.co.kr/learn/courses/30/lessons/12904

---

Problem

---

Solve

다른 분들의 풀이를 보니 대부분 구현으로 푸시긴 하였지만, DP로 풀 수 있을것 같아 DP로 도전해보았지만 해결이 안되어 다른분의 풀이를 참고하였습니다.

DP[i][j]에는 i와 j의 문자가 동일할때 팰린드롬을 만족하는지 저장되어있습니다.
예를 들어 abbc라면 DP[0][3] = true, DP[1][2] = true이고 DP[i][i]는 항상 true이게됩니다.

문자열에서 팰린드롬의 여부를 확인하기 위해서는 i의 문자와 j의 문자가 동일할때, i+1의 문자와 j-1의 문자가 동일하여 팰린드롬을 만족하는지 반복하여 확인하여 DP[i][j]를 갱신합니다.

abacda문자열이 주어진 경우,

• 1번째 문자 a와 3번째 문자 a는 동일합니다. 그리고 그 사이에 있는 두번째 문자는 팰린드롬 조건을 만족하기때문에 DP[1][1]는 true입니다. 그렇기 때문에 DP[0][2]도 true가 되게됩니다.
• 3번째 문자 a와 6번째 문자 a는 동일합니다. 그리고 그 사이에 있는 4번째, 5번째 문자는 팰린드롬 조건을 만족하지 않기 때문에 DP[3][4]는 false입니다. 그렇기 때문에 DP[2][5]도 false가 되게됩니다.

먼저 각 문자의 자신은 항상 팰린드롬 조건을 만족하기에 DP[i][i]를 true로 갱신합니다.

for(int i=0;i<s.length();i++){
	dp[i][i] = true;
}

그리고 aa의 문자열인 경우 DP[i][j]에 팰린드롬 여부를 판단하기위해 별도로 DP[i][j]를 갱신해주어야합니다.

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

그렇다면 위의 두개의 반복문을 통해 길이1,2의 [i][j]에 해당하는 문자열의 팰린드롬 여부가 DP에 저장되어있습니다.
길이 3부터 s.length()까지의 문자열이 팰린드롬을 만족하는지 순차적으로 갱신해갑니다.
길이가 작은수 부터 큰수로 늘려가며 DP[i][j]를 갱신해가므로 DP[i][j]가 팰린드롬인지 여부를 DP[i+1][j-1]을 확인할 수 있게 됩니다.

//길이 3부터 문자열의 길이까지
for(int len=3; len<=s.length(); len++){
	//i는 비교할 첫번째 index부터 index+len-1까지 팰린드롬을 만족하는지 i+1과 j-1을 비교하여 갱신할수 있습니다.
	for(int i=0;i+len<=s.length(); i++){
    	int j = i+len-1;
        //i와 j의 문자가 동일하고 i+1과 j-1의 문자가 팰린드롬을 만족하는 경우 i,j도 팰린드롬을 만족한다.
        //길이가 점점 증가하게되므로 answer에 len을 갱신해줍니다.
        if(s.charAt(i)==s.charAt(j) && dp[i+1][j-1]){
        	dp[i][j] = true;
            answer = len;
        }
    }
}

---

Code

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++){
			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;
    }
}

---

Result

---

Reference

https://velog.io/@longroadhome/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-LV.3-%EA%B0%80%EC%9E%A5-%EA%B8%B4-%ED%8C%B0%EB%A6%B0%EB%93%9C%EB%A1%AC-JS