[실전 문제] 팰린드롬 만들기

1. 문제

팰린드롬이란, 앞으로 읽으나 뒤로 읽으나 똑같은 문자열을 말한다. 예를 들어, “abcba”, “abccba” 등이 있을 수 있다. 문자열이 주어질 때, 이를 팰린드롬으로 만들기 위하여 추가해야 하는 최소의 문자 개수를 출력하는 프로그램을 작성하시오. 예를 들어, 문자열이 “abca” 로 주어질 경우, ‘b’만 추가하면 “abcba” 를 만들 수 있으므로, 이 때는 1개의 문자만 추가하면 된다. 또 다른 예로써, 문자열이 “adcba” 로 주어질 경우에는, 문자 2개를 추가해야 한다.

---

입력

첫 번째 줄에 문자열이 주어진다. 이 문자열의 길이는 1,000 을 넘지 않는다. 

출력

주어진 문자열을 팰린드롬으로 만들기 위해서 추가해야 하는 문자 개수의 최솟값을 출력한다.

예제 입력

case 1) adcba

case 2) abccbdbac

예제 출력

case 1) 2

case 2) 3

 

 

 

2. 풀이

즉, 결국 점화식은 다음과 같다.

• T(i, j)은 i부터 j까지의 문자열을 팰린드롬으로 만들기 위해 추가해야하는 문자 개수의 최솟값
• 비교하고자 하는 문자가 같을 경우 T(i, j) = T(i+1, j-1)
• 비교하고자 하는 문자가 다를 경우 T(i, j) = min(T(i-1, j), T(i, j-1)) + 1

 

import java.io.*;

public class Main {

    private static final BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    private static final BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    public static void main(String[] args) throws IOException {

        String s = br.readLine();

        int[][] arr = new int[s.length()][s.length()];

        for(int i = s.length() - 1; i >= 0 ; i--) {
            for(int j = i; j < s.length(); j++) {
                if(i == j) arr[i][j] = 0;
                else {
                    if(s.charAt(i) == s.charAt(j)) arr[i][j] = arr[i+1][j-1];
                    else arr[i][j] = Math.min(arr[i+1][j], arr[i][j-1]) + 1;
                }
            }
        }
        bw.write(arr[0][s.length()-1] + "");
        br.close();
        bw.flush();
        bw.close();
    }
}