[이코테][Java] 편집거리

문제 설명

두 개의 문자열 A와 B가 주어졌을 때, 문자열 A를 편집하여 문자열 B를 만들고자 한다.

문자열 A를 편집하여 문자열 B로 만들기 위해 사용하는 연산의 수를 '편집 거리'라고 할 때, 문자열 A를 문자열 B로 만드는 최소 편집 거리를 계산하는 프로그램을 작성하세요.

문자열을 편집할 때는 다음의 세 연산 중 한 번에 하나씩 선택하여 편집한다.

1. 삽입(insert) : 특정한 위치에 하나의 문자를 삽입합 니다.

2. 삭제(remove) : 특정한 위치에 있는 하나의 문자를 삭제합니다.

3. 교체(replace) : 특정한 위치에 있는 하나의 문자를 다른 문자로 교체합니다.

 

입력조건

• 문자열 A, B

출력조건

• 문자열 A, B간의 최소 편집 거리

입출력 예시

입력예시	출력예시
cat cut	1
sunday saturday	3

 

 

 

 

문제 풀이

• 다이나믹 프로그래밍 풀이
• 2차원 dp 테이블을 생성하고, 문자열 A와 문자열 B를 쪼개서 각 문자를 비교해서 계산한 최소 편집 거리를 테이블에 저장한다.

ex) "sunday"를 "saturday"로 변경

• 최소 편집 거리를 저장할 초기 2차원 dp 테이블을 생성한다. 

 

• 여기에서 "sun" → "satu" 로 편집하는 과정을 따로 떼내어서 연산 횟수를 계산해보았다.
  이 때, 어느 위치에서 어떤 연산을 수행했는지 화살표와 색깔로 구분해서 나타냈다.

빈 문자열 → [s, sa, sat, satu]는 문자를 하나씩 삽입해주는 연산이 필요하다. 따라서 최소편집거리는 1, 2, 3, 4 

[s, su, sun] → 빈문자열 은 문자를 하나씩 삭제해주는 연산이 필요하다. 따라서 최소편집거리는 1, 2, 3

 

문자열 "sun"의 인덱스를 i, 문자열 "satu"의 j라 하고 앞에서부터 한 문자씩 비교한다.  

• i번째 문자와 j번째 문자가 같을 경우(ex. s → s)
  • 별다른 연산이 필요하지 않기 때문에 (i-1, j-1)에서 그대로 가져온다.

• 두 문자열의 문자가 다를 경우(ex. su → sat)
  1. 삽입연산(왼쪽): su → sa의 최소편집거리에서 삽입 연산을 한 번 수행한다.(t를 삽입하는 연산)
  2. 삭제연산(위쪽): s → sat의 최소편집거리에서 삭제 연산을 한 번 수행한다.(u를 삭제하는 연산)
  3. 교체연산(왼쪽위): s → sa의 최소편집거리에서 교체 연산을 한 번 수행한다.(u를 t로 교체하는 연산)
• 위의 세가지 연산 중에서 편집 거리가 가장 작은 것을 저장한다.

 

 

• 위의 규칙을 적용해서 "sunday"를 "saturday"로 편집하기 위한 dp 테이블을 완성해보면 다음과 같다.
  따라서 최소 편집 거리는 3이다.

• 점화식으로 나타내면 다음과 같다.

1. 두 문자가 동일하다면, 왼쪽 위와 동일하다.

dp[i][j] = dp[i-1][j-1]

 

2. 두 문자가 동일하지 않다면, 왼쪽(삽입), 왼쪽 위(교체), 위(삭제) 중 가장 작은 값에 1을 더 한 값이 최소 편집 거리가 된다.

dp[i][j] = min(dp[i][j - 1], dp[i - 1][j], dp[i - 1][j - 1])+ 1

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

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        String str1 = br.readLine();
        String str2 = br.readLine();

        int[][] dp = new int[5001][5001];   //최소 편집 거리 계산 dp 테이블

        //최소 편집 거리 계산
        for (int i = 0; i < str1.length() + 1; i++) {
            for (int j = 0; j < str2.length() + 1; j++) {
                //첫번째 행과 열은 공백과 문자가 비교되는 부분으로 따로 처리
                if (i == 0) {
                    dp[i][j] = j;
                } else if (j == 0) {
                    dp[i][j] = i;
                } else {
                    //문자가 같을 경우, 왼쪽 위 그대로 대입
                    if (str1.charAt(i - 1) == str2.charAt(j - 1)) {
                        dp[i][j] = dp[i - 1][j - 1];
                    } else if (str1.charAt(i - 1) != str2.charAt(j - 1)) {
                        //문자가 다를 경우, 1. 삽입(왼쪽), 2.삭제(위쪽), 3. 교체(왼쪽 위) 중 최소값 + 1
                        dp[i][j] = 1 + Math.min(dp[i][j - 1], Math.min(dp[i - 1][j], dp[i - 1][j - 1]));
                    }
                }
            }
        }
        System.out.println(dp[str1.length()][str2.length()]);
    }
}

 

 

처음에 문제를 읽었을 때 주어진 연산을 사용해서 문자열 A을 문자열 B로 만드는 최소 연산 횟수를 구하는 단순한 문제라고 생각했다.

내가 생각한 풀이는

1. 문자열 A를 B로 편집하는데 사용되는 최소연산횟수를 저장하는 dp 테이블을 생성한다.

2. 문자열 A와 B를 쪼개서 한문자씩 비교한다. 이 때, dp[i]를 구하기 위해서 문자열 A와 B의 i번째 문자를 비교한다.

    문자열 A와 B의 i번째 문자가 같으면 dp[i] = dp[i-1], 서로 다를 경우 삽입 or 삭제 or 교체 연산을 수행해야하기 때문에 dp[i] = dp[i-1] + 1

여기까지는 생각을 했다.

그런데 여기서 어떠한 규칙으로 삽입, 삭제, 교체 연산이 수행되는지 찾지 못했다.

또한 내가 생각한 방식은 dp테이블이 1차원 배열이라서 두 문자열의 인덱스 변수가 같기 때문에 두 문자열의 길이가 다를 경우 실행할 수 없다(?)

그래서 이 이후로는 풀이가 떠오르지 않아서 다른 분의 풀이를 보고 문제를 해결했다.

 

---

[참고서적]

이것이 취업을 위한 코딩 테스트다 with 파이썬 by 나동빈

https://velog.io/@embeddedjune/알고리즘-이것이-코딩-테스트다-DP-Q36-편집-거리