[PS] 백준 15483번: 최소편집

|

문제

내가 이해한 문제 내용

삽입,삭제,치환의 3가지 연산이 주어졌을 때 문자열 $A$를 문자열 $B$로 바꾸는데 필요한 최소 편집 횟수를 구하시오.

접근 방식

  • 처음엔 단순하게 문자열 비교로 보면서 1차원적으로 접근했으나 풀 수 없었고 질문란을 보니 LCS랑 연관있는 것임을 알았다.

  • 그래서 LCS를 다시 공부했고 점화식을 파악했지만 단순 LCS로는 해결이 불가능했다.

  • 풀이를 보니 LCS랑 풀이방식이 비슷했다.

    • 예를 들어 abccde로 만드는 최소편집 횟수를 구한다면 2차원 배열을 만든 뒤 특정 문자열의 접두사에서 다른 문자열의 접두사를 만드는데 필요한 모든 최소편집 횟수를 구하면 된다.

    • dp[i][j] = "abc"의 길이 i 접두사를 "cde"의 길이 j 접두사로 만드는데 필요한 최소편집횟수
      // 접두사의 마지막 문자가 같을 때
      dp[i][j] = dp[i-1][j-1]
      // 접두사의 마지막 문자가 다를 때
      dp[i][j] = min(dp[i-1][j-1],min(dp[i-1][j],dp[i][j-1])) + 1
      
    • 마지막 문자가 같다는 것은 현재 문자를 제외한 경우를 그대로 추가해주면 되는 것이므로 dp[i-1][j-1]값을 사용하면 된다.

    • 마지막 문자가 다르다는 것은 이전 값을 그대로 쓸 수 없으므로 경우를 또 나눠주어야 한다.

      • 왼쪽에서 삽입연산을 하는 경우
      • 대각선에서 교체연산을 하는 경우
      • 위쪽에서 삽입연산을 하는 경우
      • 위의 3가지 경우가 존재하기 때문에 1을 더해주는 것이다.

어려웠던 점 & 배운 점

  • LCS를 다시 생각하니 생각이 안났던 점이 어려웠다.
  • LCS를 그대로 사용하지 않고 다른 방식으로 사용하는 점이 어려웠는데 이래서 코드가 아니라 개념과 아이디어가 중요하다는 것을 다시 한 번 깨달았다.

시간복잡도

  • $O(N^2)$

코드

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

public class Main {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        String s1 = br.readLine(),s2 = br.readLine();
        int len1 = s1.length(), len2 = s2.length();

        int dp[][] = new int[1001][1001];

        for(int i=0; i<=len1; i++) dp[0][i] = i;
        for(int i=0; i<=len2; i++) dp[i][0] = i;

        for(int i=1; i<=len2; i++){
            for(int j=1; j<=len1; j++){
                if(s1.charAt(j-1)==s2.charAt(i-1)) {
                    dp[i][j] = dp[i-1][j-1];
                }
                else {
                    dp[i][j] = Math.min(Math.min(dp[i-1][j],dp[i][j-1]),dp[i-1][j-1]) + 1;
                }
            }
        }

        bw.write(String.valueOf(dp[len2][len1]));
        bw.flush();

        br.close();
        bw.close();
    }
}