문제 링크
문제
티어: 골드 1
알고리즘: dp
문자열 O에서 문자열 N까지 문자열 거리는 O를 N과 같게 만들기 위해 필요한 문자열 삽입의 최솟값이다. 문자열 삽입은 O의 어느 위치에서건 가능하다. 예를 들어, O가 “gosrl"일 때, ”sip gi"을 r이전에 삽입한다면 "gossip girl“이 된다.
문자열 O와 문자열 N이 주어질 때, 두 문자열의 거리를 출력하는 프로그램을 작성하시오.
입력
첫째 줄에 문자열 O, 둘째 줄에 문자열 N이 주어진다. 문자열의 길이는 최대 1,000이다. 문자열은 아스키 코드의 값이 32보다 크거나 같고, 126보다 작거나 같은 문자로만 이루어져 있다.
출력
첫째 줄에 문자열 O와 문자열 N의 문자열 거리를 출력한다. 만약 O를 N으로 만들 수 없다면 -1을 출력한다.
풀이
문자열 O에서 문자열 N까지 문자열 거리를 출력해야 한다. 만약 만들 수 없다면 -1를 출력한다.
예제 입력 1
hello fine
hello, how are you? I'm fine thank you and you?
O를 삽입을 통해서 N으로 만들어 줘야 하는데, 삭제나 순서를 변환하는 연산은 없기 때문에
첫 번째 h는 N 문자열의 문자 중 h에 반드시 매칭되어야 한다.
그래서 h는 N의 1 번째 8 번째, 31 번째에 반드시 매칭된다.
매칭되었다면, 횟수는 몇 일까? 그전 문자들이 있다면 삽입해야 되기 때문에 1이 되지만
그 전 문자들이 없다면 0이 된다.
그래서 N의 1 번째에 매칭되면 0이고, 8 번째에 매칭되면 1이 된다.
다음 e 또한 똑같이 매칭시키면 된다. N에서의 탐색은 2 번째부터 가능하다. h가 매칭될 최소 공간이 1 번째이기 때문이다.
매칭되고 나면, 횟수는 몇 일까? h가 어떻게 매칭되었는지에 따라서 그 값은 달라진다.
그래서 e가 N의 14 번째 문자와 매칭되었다면 h는 첫 번째 매칭되었을 때가 최솟값이 될 것이다. (h에서 앞에 ello, how ar만 넣어주면 되기 때문)
그러면 dp를 어떻게 정의해 줄 수 있을까? 만약 O의 2 번째(he)까지와 N의 14 번째(hello, how are)까지 매칭 후 삽입을 했다면, 그 값 중 최솟값을 활용하는 것이 최적해일 것이다.
그래서 dp는 dp[O.length()][N.length()]로 정의해 줄 수 있다.
예를 들어 dp[2][14]는 O의 2 번째(he)까지와 N의 14 번째(hello, how are)까지 매칭 후 삽입을 했을 때의 최소 횟수를 의미한다.
점화식은 dp[a][b] = dp[a - 1][b - 1]이고, 만약 dp[a - 1][b - 1]이 존재하지 않는다면 dp[a][b] 또하 존재하지 않는다.
(dp[a - 1][b - 1]은 항상 최솟값을 담고 있어야 함을 유의해야 한다.)
점화식까지 잘 정의했다면, 구현은 어렵지 않을 것이다. 자세한 구현 사항은 코드를 참고하길 바란다.
이 풀이의 시간 복잡도는 O(1000 x 1000)이다.
소스 코드
import java.io.*;
import java.util.*;
public class Main {
public static void main(String args[]) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String O = br.readLine();
String N = br.readLine();
int[][] dp = new int[O.length() + 1][N.length() + 1];
for(int i=1; i<=N.length(); i++) {
dp[0][i] = 1;
}
for(int i=1; i<=O.length(); i++) {
char std = O.charAt(i - 1);
int ind = -1;
for(int j=i; j<=N.length(); j++) {
if(std == N.charAt(j - 1)) {
//같다면
if(dp[i - 1][j - 1] != -1) {
if(ind == -1) {
dp[i][j] = dp[i - 1][j - 1];
ind = j;
} else {
if(dp[i - 1][j - 1] <= dp[i][ind]) {
dp[i][j] = dp[i - 1][j - 1];
ind = j;
} else {
dp[i][j] = 1 + dp[i][ind];
}
}
} else {
dp[i][j] = -1;
}
} else {
//다르면
if(ind == -1) {
dp[i][j] = -1;
} else {
dp[i][j] = 1 + dp[i][ind];
}
}
}
}
System.out.println(dp[O.length()][N.length()]);
}
}