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

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

프로그래머스

 

코딩테스트 연습 > 연습문제 > 가장 긴 팰린드롬

 

문제 설명

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

제한 사항

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

 

문제 접근

"abacde" 의 팰린드롬 최대 길이를 DP를 통해서 한번 구해보자 

 

먼저 들어온 문자열을 char [] 배열에 넣어준다. 

매번 chatAt()으로 구하는 시간 보다 미리 구해놓고 배열에서 꺼내어 쓰는게 더 빠르다.

 

boolean [][] DP = new boolean [size][size] 를 선언 

항상 점화식을 세우고 시작하는게 좋다. 

 

여기서 DP[1][3] 은 무엇을 의미할까?

aba 는 팰린드롬인가?를 의미한다.  팰린드롬이면 true 

처음 배열을 초기화하면 기본이 false이기 때문에 팰린드롬이면 채워 나가는 방식이다.

 

자 다시 DP[2][4]는? 

bac가 팰린드롬인가?를 의미한다. 

 

이건 점화식이라고 하기보다는 그냥 값의 의미를 말한다.

DP에서의 점화식은 일종의 가설이다. 

 

가설? 그게 무슨 말..?

여기 도미노가 5개짜리가 있다고 가정하자. 각 도미노들은 1개 도미노가 넘어지면 다음 도미노도 넘어질 만큼의 간격으로 도미노가 세워져있다.

우린 첫 번째 도미노가 넘어지면 모든 도미노가 차례대로 넘어진다는 것을 알 수 있다. 

DP도 똑같다. 처음 DP 값들이 채워지면 차례대로 다음 DP 값들도 채워지는것이다. ( - 바킹독 - )

 

이를 통해 엄청나게 많은 경우의 수를 짧은 시간 복잡도로 구하는 게 가능하다.

모든 경우의 수를 구하는 완전 탐색(백트래킹)과 정반대의 성질이다.

 

자 이번 문제의 가설은 무엇일까?

 

- 길이가 1 - 

먼저 길이가 1인 팰린드롬부터 구해보자

DP[1][1] 는 문자 1개를 의미한다. a를 뒤집으면 a  무조건 팰린드롬이다 -> 채우자 true로 

 

- 길이가 2 - 

길이가 2인 팰린드롬은 어떻게 구할까?
DP[1][2] 는 ab 이다. ab는 뒤집으면 ba이다. 뒤집어서 같을려면 char[1] 과 char[2]가 같아야 한다.

 

- 길이가 3 - 

DP[1][3] 는 aba 이다. 가운데 문자는 상관 없이 char[1] 과 char[3]이 같으면 팰린드롬이다. 

 

- 길이가 4 -

DP[1][4]는 abac이다. 우린 이미 ab ba ac 가 팰린드롬인지 다 구했다. 

그럼 어떻게 간단하게 abac가 팰린드롬인지 아닌지 확인할까?

앞에 길이가 1, 2, 3에서 구했던 방법처럼 맨 앞과 맨 뒤가 똑같은지 확인하고 

가운데인 ba가 팰린드롬인지 확인하면 된다.

DP[1][4]의 팰린드롬 조건을 정리하면 

char[1] == char[4] , DP[2][3] = ture 이다.

만약 이 두 조건이 성립하면 

DP[1][4] 또한 true 이다.

 

자 이제 도미노를 박살내자!

 

정답 코드

class Solution{
    public int solution(String s){
        int answer = 0;
        int size = s.length();
        char [] input = new char[size];
        for(int i = 0; i < size; i++){
            input[i] = s.charAt(i);
        }  
        boolean [][] pa = new boolean [size][size];
        for(int i = 0; i < size; i++){
            for(int j = 0; j < size; j++){
                int target = j + i;
                if(target > size - 1) break;
                if(input[j] != input[target]) continue;
                if(i <= 1){
                    pa[j][target] = true;
                    if(target - j + 1 > answer){
                        answer = target - j + 1;
                    }
                    continue;
                }
                if(pa[j+1][target-1]){
                    pa[j][target] = true;
                    if(target - j + 1 > answer){
                        answer = target - j + 1;
                    }
                }
            }
        }   
        return answer;
    }
}