문제 개요
세 개의 문자열 s1, s2, s3가 주어졌을 때, s3가 s1과 s2의 문자들을 서로 섞어 배치한 결과(인터리빙)로 만들어질 수 있는지 판별하는 문제입니다.
예를 들어 s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"이라면, s3는 s1과 s2를 적절히 교차 배치해 만들 수 있으므로 결과는 true(1)가 됩니다.
접근 방법: 메모이제이션을 활용한 동적 계획법(DP)
이 문제는 재귀 호출과 메모이제이션을 결합한 동적 계획법으로 효율적으로 해결할 수 있습니다. 핵심 아이디어는 s1의 앞부분 i개 문자와 s2의 앞부분 j개 문자를 사용해 s3의 앞부분 k개 문자를 만들 수 있는지를 상태로 정의하는 것입니다.
풀이 단계
- solve()라는 재귀 메서드를 정의합니다. 이 메서드는 s1, s2, s3, 3차원 배열 dp, 그리고 인덱스 i, j, k를 인자로 받습니다.
- i = 0, j = 0, k = 0이면 모든 문자열을 소진한 것이므로 true를 반환합니다.
- dp[i][j][k] 값이 -1이 아니라면 이미 계산된 상태이므로 해당 값을 그대로 반환합니다.
- ans를 false로 초기화합니다.
- i > 0이고 k >= 0이며 s1[i] == s3[k]인 경우, ans := solve(s1, s2, s3, dp, i - 1, j, k - 1)로 갱신합니다.
- j > 0이고 k >= 0이며 s2[j] == s3[k]인 경우, ans := ans OR solve(s1, s2, s3, dp, i, j - 1, k - 1)로 갱신합니다.
- dp[i][j][k]에 ans 값을 저장하고 반환합니다.
메인 함수에서의 처리
- n := s1의 길이, m := s2의 길이, o := s3의 길이로 설정합니다.
- 인덱스 계산을 편하게 하기 위해 s1, s2, s3 앞에 공백 한 칸을 추가합니다(1-based 인덱싱).
- (n + 1) × (m + 1) × (o + 1) 크기의 3차원 배열을 만들고 모든 값을 -1로 초기화합니다(-1은 아직 계산되지 않은 상태를 의미).
- solve(s1, s2, s3, dp, n, m, o)의 결과를 반환합니다.
구현 예시
아래 코드를 통해 더 자세히 이해해 보겠습니다.
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
bool solve(string s1, string s2, string s3, vector < vector < vector <int>>>& dp, int i, int j, int k){
if(i ==0 && j == 0 && k == 0)return true;
if(dp[i][j][k] !=-1)return dp[i][j][k];
bool ans = false;
if(i > 0 && k >= 0 && s1[i] == s3[k]){
ans = solve(s1, s2, s3, dp, i - 1, j, k - 1);
}
if(j >0 && k >=0 && s2[j] == s3[k]){
ans |= solve(s1, s2, s3, dp, i, j - 1, k - 1);
}
return dp[i][j][k] = ans;
}
bool isInterleave(string s1, string s2, string s3) {
int n = s1.size();
int m = s2.size();
int o = s3.size();
s1 = " " + s1;
s2 = " " + s2;
s3 = " " + s3;
vector < vector < vector <int>>> dp(n + 1, vector < vector <int>>(m + 1, vector <int> (o + 1, -1)));
return solve(s1, s2, s3, dp, n , m , o );
}
};
main(){
Solution ob;
cout << (ob.isInterleave("aabcc", "dbbca", "aadbbcbcac"));
}입력
"aabcc", "dbbca", "aadbbcbcac"
출력
1
복잡도 분석
각 상태 (i, j, k)는 최대 한 번만 계산되므로 시간 복잡도는 O(n × m × o)이고, 3차원 DP 배열을 사용하므로 공간 복잡도 역시 O(n × m × o)입니다. 단순 재귀로 풀 경우 지수 시간이 걸릴 수 있는 문제를 메모이제이션 덕분에 다항 시간 안에 해결할 수 있습니다.