36.편집 거리

📍 문제 설명

두 개의 문자열 A와 B가 주어졌을 때, 문자열 A를 편집하여 문자열 B로 만들고자 합니다. 문자열 A를 편집할 때는 다음의 세 연산 중에서 한 번에 하나씩 선택하여 이용할 수 있습니다.

 

1. 삽입(Insert): 특정한 위치에 하나의 문자를 삽입합니다.
2. 삭제(Remove): 특정한 위치에 있는 하나의 문자를 삭제합니다.
3. 교체(Replace): 특정한 위치에 있는 하나의 문자를 다른 문자로 교체합니다.

이때 편집 거리란 문자열 A를 편집하여 문자열 B로 만들기 위해 사용한 연산의 수를 의미합니다. 문자열 A를 문자열 B로 만드는 최소 편집 거리를 계산하는 프로그램을 작성하세요. 예를 들어 "sunday"와 "saturday"의 최소 편집 거리는 3입니다.

---

입력

두 문자열 A와 B가 한줄에 하나씩 주어집니다.

각 문자열은 영문 알파벳으로만 구성되어 있으며 , 각 문자열의 길이는 1보다 크거나 같고, 5,000보다 작거나 같습니다.

---

출력

최소 편집 거리를 출력합니다.

 

💡 접근

행에 있는 문자열을 열에 있는 문자열로 만들기 위한 최소 거리를 구해야함

현재 좌표에 왼쪽 위는 문자가 같을 때 

삽입시에는 왼쪽 열의 값 + 1

삭제시에는 위쪽 행의 값 + 1

교체시에는 왼쪽 열 위쪽 행의 값 + 1

이 중 최솟값으로 계속 기록해나간다.

dp[n][m]이 A 문자열을 B 문자열로 바꾼 최소 편집거리가 된다.

 

👩‍💻 코드

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner kb = new Scanner(System.in);

        String a = kb.nextLine();
        String b = kb.nextLine();

        int n = a.length();
        int m = b.length();

        //문자당 최소 편집 거리를 구하는 dp 테이블 초기화
        int[][] dp = new int[n+1][m+1];
        // DP 테이블 초기 설정
        for (int i = 1; i <= n; i++) {
            dp[i][0] = i;
        }
        for (int j = 1; j <= m; j++) {
            dp[0][j] = j;
        }

        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= m; j++) {
                //문자가 같다면 거리가 변하는게 없음
                if(a.charAt(i - 1) == b.charAt(j - 1)) {
                    dp[i][j] = dp[i-1][j-1];
                }
                //문자가 다르면 삽입, 삭제, 교체시 최솟값을 기록
                else {
                    dp[i][j] = Math.min(dp[i][j-1], Math.min(dp[i-1][j], dp[i-1][j-1])) + 1;
                }
            }
        }
        System.out.println(dp[n][m]);
    }
}