[BaekJoon] 15483 최소 편집 (Java)

1.  문제 링크

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

2.  문제

3.  소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    static char[] from;
    static char[] to;

    static void input() {
        Reader scanner = new Reader();

        from = scanner.nextLine().toCharArray();
        to = scanner.nextLine().toCharArray();
    }

    /*
     * 문자열 A를 from, 문자열 B를 to라고 지칭한다
     * dp[fromIdx][toIdx]
     *  - from 문자열의 첫 번째 문자부터 fromIdx번째 문자까지의 부분 문자열에서
     *    to 문자열의 첫 번째 문자부터 toIdx번째 문자까지의 부분 문자열을 만드는 데에 필요한 최소 편집 횟수
     *
     * 두 가지의 경우로 나눠서 생각한다
     *  1. fromIdx번째 문자와 toIdx번째 문자가 같은 경우
     *      - dp[fromIdx][toIdx] = dp[fromIdx - 1][toIdx - 1]
     *          - 현재 문자가 빠진 두 부분 문자열 각각에 현재 문자가 추가된 것인데,
     *            같은 문자이기 때문에 추가적인 편집 작업이 없다
     *  2. fromIdx번째 문자와 toIdx번째 문자가 다른 경우
     *      - dp[fromIdx][toIdx] = min(dp[fromIdx - 1][toIdx - 1], min(dp[fromIdx][toIdx - 1], dp[fromIdx - 1][toIdx])) + 1
     *          - 새로운 문자가 추가됨에 따라 추가적인 편집 작업이 필요하기 때문에 1을 더하여 편집 횟수를 구한다
     *          - 이전 작업에는 3가지 경우가 존재하기 때문에 그 작업들 중 최소 편집 횟수에 1을 더하여 최소 편집 횟수를 구한다
     */
    static void solution() {
        int[][] dp = new int[from.length + 1][to.length + 1];
        init(dp);

        for (int fromIdx = 1; fromIdx < dp.length; fromIdx++) {
            for (int toIdx = 1; toIdx < dp[fromIdx].length; toIdx++) {
                if (from[fromIdx - 1] == to[toIdx - 1]) {
                    dp[fromIdx][toIdx] = dp[fromIdx - 1][toIdx - 1];
                } else {
                    dp[fromIdx][toIdx] = Math.min(dp[fromIdx - 1][toIdx - 1],
                            Math.min(dp[fromIdx][toIdx - 1], dp[fromIdx - 1][toIdx])) + 1;
                }
            }
        }

        System.out.println(dp[from.length][to.length]);
    }

    static void init(int[][] dp) {
        for (int idx = 0; idx < dp.length; idx++) {
            dp[idx][0] = idx;
        }
        for (int idx = 0; idx < dp[0].length; idx++) {
            dp[0][idx] = idx;
        }
    }

    public static void main(String[] args) {
        input();
        solution();
    }

    static class Reader {
        BufferedReader br;
        StringTokenizer st;

        public Reader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String nextLine() {
            String str = "";
            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }
    }
}