문제
문자열 B에서 연속 부분 문자열을 최소 횟수로 제거하여, 남은 부분이 A와 같아지도록 하라. 불가능하면 -1을 출력한다.
입력
첫째 줄에 문자열 A, 둘째 줄에 문자열 B가 주어진다.
출력
최소 제거 횟수를 출력한다. 불가능하면 -1을 출력한다.
예제
| 입력 | 출력 |
|---|---|
abc aXbYc | 2 |
풀이
2차원 DP로 매칭 상태와 삭제 상태를 동시에 관리한다.
dp[i][j]: A의 i번째까지 매칭하면서 B의 j번째까지 처리했을 때 [매칭 중 최소 삭제 수, 삭제 중 최소 삭제 수]A[i] == B[j]이면 매칭 상태를 이전 상태에서 이어받는다- 불일치 시 삭제 중 상태를 유지하거나, 매칭 상태에서 새로운 삭제를 시작한다
- A가 B보다 길면 즉시 -1을 반환한다
핵심 아이디어: 연속 삭제는 1회로 카운트되므로, 매칭/삭제 두 상태를 구분하여 삭제 시작 시점만 카운트한다.
코드
const solution = ([a, b]) => {
const na = a.replace(" ", "").length;
const nb = b.replace(" ", "").length;
const INF = 1_000;
if (na > nb) return -1;
const dp = Array.from(Array(na + 1), () =>
Array.from(Array(nb + 1), () => [0, 0])
);
dp[0][0] = [0, INF];
for (let i = 1; i <= nb; i++) dp[0][i] = [INF, 1];
for (let i = 0; i < na; i++) {
for (let j = 0; j <= i; j++) dp[i + 1][j] = [INF, INF];
for (let j = i; j < nb; j++)
dp[i + 1][j + 1] = [
a[i] === b[j] ? Math.min(dp[i][j][0], dp[i][j][1]) : INF,
Math.min(dp[i + 1][j][0] + 1, dp[i + 1][j][1]),
];
}
const result = Math.min(dp[na][nb][0], dp[na][nb][1]);
return result >= INF ? -1 : result;
};
const fs = require("fs");
const input = fs.readFileSync("/dev/stdin").toString().trim().split("\n");
console.log(solution(input));복잡도
- 시간: O(N × M) — N, M은 각 문자열 길이
- 공간: O(N × M)