이코테 - 편집거리 with JAVA

 

 

 

해결

- 동작은 삽입, 삭제, 교체가 가능하다고 문제에서 제시한다.

sunday를 saturday로 변경한다고 가정하자

2차원 테이블은 다음과 같이 구성된다.

(2차원 테이블 : 가장 왼쪽열에 있는 sunday를 가장 위쪽행에 있는 saturday로 변경하는 비용 테이블, 0은 빈문자열을 의미)

	0	S	A	T	U	R	D	A	Y
0	0 (0, 0)	1	2	3	4	5	6	7	8
S	1	0	1	2	3	4	5	6	7
U	2
N	3
D	4
A	5
Y	6

- 예를들어, (2, 4)는 s1의 처음부터 두번째까지 글자를 s2의 처음부터 4번째 글자로 만드는 가장 적은 연산수이다.

 

삽입 : 왼쪽 칸 + 1

삭제 : 위쪽 칸 + 1

교체 : 왼쪽 위칸 +1

 

삽입, 삭제, 교체 중 가장 작은 값을 찾아 선택 후 + 1을 더해 갱신한다.

 

 

코드

import java.util.*;

// 편집 거리
public class Q6 {

    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        // 두개의 문자열 입력 받기
        String str1 = sc.next();
        String str2 = sc.next();
        // 로직 함수 실행
        edit_dist(str1, str2);
    }

    public static void edit_dist(String str1, String str2){
        // 각 문자열의 길이
        int n = str1.length();
        int m = str2.length();

        // 2차원 dp 초기화
        int[][] dp = new int[n+1][m+1];
        for(int i=1; i<n+1; i++){
            dp[i][0] = i;
        }
        for(int i=1; i<m+1; i++){
            dp[0][i] = i;
        }

        // 메인 로직
        for(int i=1; i<n+1; i++){
            for(int j=1; j<m+1; j++){
                // 두 문자가 같은 경우
                // - 행과 열에 해당하는 문자가 서로 같다면 왼쪽 위에 해당하는 수를 그대로 대입
                if(str1.charAt(i-1) == str2.charAt(j-1)){
                    dp[i][j] = dp[i-1][j-1];
                }
                // 두 문자가 다른 경우
                // - 행과 열에 해당하는 문자가 서로 다르다면, 왼쪽, 위쪽, 왼쪽 위에 해당하는 수 중
                // 가장 작은 수에 1을 더해 대입
                else{
                    int result = Math.min(dp[i][j-1], dp[i-1][j]);
                    result = Math.min(result, dp[i-1][j-1]);
                    dp[i][j] = 1 + result;
                }
            }
        }

        System.out.println(dp[n][m]);
    }
}