팰린드롬 DP로 풀어보기

 

 

https://www.acmicpc.net/problem/10942

[10942. 팰린드롬?] 풀러가보자

 

 

 

기존의 투포인터 방식의 풀이

    public static boolean isP(int lt, int rt) {

        while (lt < rt) {

            if (arr[lt] == arr[rt]) {
                return false;
            }

            lt++;
            rt--;
        }

        return true;
    }

 

 

위의 경우, 이분탐색은 일반적으로 O(logN)의 빠른 시간 효율성을 가지지만 만약 주어진 배열의 모든 조합 (i, j까지의 부분 배열에 대하여) 확인한다고 치면 주어진 배열의 양 끝에서부터 중앙으로 비교하며 최악의 경우 O(N)을 갖게 될 수 있다.

그렇게 되면 총 시간복잡도는 질문의수(M) * 수열의 길이(N) 만큼이므로 비효율적이다. 생각해보면 그 모든 케이스 안에서도 중첩된 경우의 수가 있으니, 이를 DP로 해결하고자 하는 아이디어가 나올 수 있다.

 

DP를 통한 풀이

배열의 길이가 1인 경우

분할정복처럼, 우선 확인하고자 하는 팰린드롬 타깃 배열의 길이가 1인 경우를 먼저 생각해본다. 무조건 팰린드롬이다.

// 배열이 주어졌다.
arr = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();

// 각 배열의 부분수열에 대해 펠린드롬인지 확인해본다
boolean[][] dp = new boolean[N][N];

for (int i = 0; i < N; i++) {
	dp[i][i] = true; // 한자리는 다 가능
}

 

배열의 길이가 2인 경우

두 개의 원소가 같다면 팰린드롬이다.

for (int i = 0; i < N - 1; i++) {
    if (arr[i] == arr[i + 1]) {
        dp[i][i + 1] = true;
    }
}

 

배열의 길이가 3 이상인 경우

여기서 부터 점화식을 생각해보면, 간단히 dp[i][j] = dp[i+1][dp[j-1] && ( arr[i] == arr[j])  임을 알 수 있다

즉 양끝을 제외한 내부가 이전에 팰린드롬이었는지를 확인해보면 된다

for(int len =3; len <= N; len++){
	
    // 시작점
    for(int s =0; s<= N-len; s++){
    	int e = s+len-1; // 끝 점  ---> dp[s][s+len-1]
    	
        if ( arr[s] == arr[e] && dp[s+1][e-1]){
        	dp[s][e] = true;
        }
    }
}