[BaekJoon] 1230번 - 문자열 거리 [Java][C++]

문제 링크

---

1. 문제 풀이

문자열 O를 문자열 N과 같게 만들기 위해 필요한 문자열 삽입의 최솟값을 찾는 문제로 다이나믹 프로그래밍을 활용하면 해결할 수 있다.

dp 테이블은 문자열 O의 $0$ 번째 인덱스부터 $i$ 번째 인덱스를 갖는 접두어와 문자열 N의 $0$ 번째 인덱스부터 $j$ 번째 인덱스를 갖는 접두어를 비교하기 위해 2차원 dp를 활용했으며, 이때 접두어의 끝 문자를 매칭하는 문자로 처리할지 새로 삽입하는 문자로 처리할지 분기를 위해 $match$ 와 $insert$ 두 개의 테이블을 만들었다.

문자열 N의 $j$ 번 문자에 대해 삽입으로 처리하는 경우는 이전의 $j-1$ 번 문자를 삽입으로 처리하던 상황에서 이어서 삽입하거나, 이전의 $j-1$ 번 문자는 매칭됐던 상황에서 새롭게 삽입할 수 있다. 따라서 $insert[i][j] = min(match[i][j-1] + 1, insert[i][j-1])$ 이 된다.

문자열 N의 $j$ 번 문자에 대해 매칭으로 처리하는 경우는 이전의 $i-1$ 번 문자와 $j-1$ 번 문자를 매칭으로 처리한 상황에서 이어서 매칭으로 처리할 수도 있고, 이전의 $i-1$ 번 문자와 $j-1$ 번 문자를 삽입으로 처리한 상황에서 새롭게 매칭으로 처리할 수도 있다. 따라서 $match[i][j] = min(match[i-1][j-1], insert[i-1][j-1])$ 이 된다.

---

2. 코드

1. 풀이 [Java]

import java.io.*;

public class Main {

    static final int INF = 1001;

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

        char[] str1 = br.readLine().toCharArray();
        char[] str2 = br.readLine().toCharArray();
        int n = str1.length;
        int m = str2.length;

        int[][] match = new int[1 + n][1 + m];
        int[][] insert = new int[1 + n][1 + m];
        for (int i = 0; i <= n; i++) {
            for (int j = 0; j <= m; j++) {
                match[i][j] = insert[i][j] = INF;
            }
        }

        match[0][0] = 0;
        for (int j = 1; j <= m; j++) {
            insert[0][j] = 1;
        }

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (str1[i - 1] == str2[j - 1]) {
                    match[i][j] = Math.min(match[i - 1][j - 1], insert[i - 1][j - 1]);
                }
                insert[i][j] = Math.min(match[i][j - 1] + 1, insert[i][j - 1]);
            }
        }

        int result = Math.min(match[n][m], insert[n][m]);
        if (result == INF) {
            System.out.println(-1);
        } else {
            System.out.println(result);
        }
    }
}

2. 풀이 [C++]

#include <bits/stdc++.h>
using namespace std;

const int INF = 1001;
int match[1001][1001];
int insert[1001][1001];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    string s1, s2;
    getline(cin, s1);
    getline(cin, s2);

    int n = s1.size();
    int m = s2.size();

    for (int i = 0; i <= n; i++) {
        for (int j = 0; j <= m; j++) {
            match[i][j] = insert[i][j] = INF;
        }
    }

    match[0][0] = 0;
    for (int j = 1; j <= m; j++) {
        insert[0][j] = 1;
    }

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (s1[i - 1] == s2[j - 1]) {
                match[i][j] = min(match[i - 1][j - 1], insert[i - 1][j - 1]);
            }
            insert[i][j] = min(match[i][j - 1] + 1, insert[i][j - 1]);
        }
    }

    int res = min(match[n][m], insert[n][m]);
    if (res == INF) {
        cout << -1;
    } else {
        cout << res;
    }
}

---