너무 쉬운 문제인데 너무 어렵게 생각해서 며칠의 시간이 갈린지 모르겠다.
문자열 A, B로 생각했을 때,
B를 하나씩 순차적으로 탐색하면서 A의 인덱스 별로 최장 길이를 담은 DP 배열을 만들어
A 내 해당 인덱스의 문자와 B의 현재 탐색중인 문자가 같으면 최장 길이+1을 해서 갱신 해 준다.
vector<vector<int>> dp(1, vector<int>(A.size()));
for (int b_i = 0; b_i < B.length(); b_i++) {
auto b = B[b_i];
int longest = 0;
int long_idx = -1;
vector<int> cur_dp(A.size());
for (int a_i = 0; a_i < A.length(); a_i++) {
auto a = A[a_i];
if (b == a) {
cur_dp[a_i] = longest + 1;
}
else {
cur_dp[a_i] = dp[b_i][a_i];
}
if (dp[b_i][a_i] > longest) {
longest = dp[b_i][a_i];
}
}
dp.push_back(cur_dp);
}이렇게 하면 dp의 마지막 인덱스 (b 탐색이 모두 끝난 후의 상태)에서 최장 값을 찾으면 그 값이 정답이 된다.
사실 dp[B.length][A.length] 사이즈의 배열은 필요 없는데, 바로 이전 값만 참고하기 때문에,
1차원의 크기는 2로만 두어도 되며, 혹은 추가적으로 검토를 해서 1차원으로 만들 수도 있을 텐데,
공간복잡도를 고민해야 할 문제는 아니기 때문에 넘어가도 된다고 우선 판단했다.
이렇게 최장값을 찾는 것은 쉽지만, 이 문자열을 복원하는 과정이 내게는 의외로 너무 큰 걸림돌이였다.
너무 간단해 보이는데 집중을 잘 못해서인지 수많은 시간을 낭비했다..
우선적으로 적용해 볼 수 있는 방법은 dp[b_i][a_i]에 값을 갱신해 줄 때 최장 값의 위치를 기록하는 방법이다.
vector<vector<int>> dp(1, vector<int>(A.size()));
vector<vector<int>> dp_idx(1, vector<int>(A.size()));
for (int b_i = 0; b_i < B.length(); b_i++) {
auto b = B[b_i];
int longest = 0;
int long_idx = -1;
vector<int> cur_dp(A.size());
vector<int> cur_dpidx(A.size());
for (int a_i = 0; a_i < A.length(); a_i++) {
auto a = A[a_i];
if (b == a) {
cur_dp[a_i] = longest + 1;
cur_dpidx[a_i] = long_idx;
}
else {
cur_dp[a_i] = dp[b_i][a_i];
cur_dpidx[a_i] = dp_idx[b_i][a_i];
}
if (dp[b_i][a_i] > longest) {
longest = dp[b_i][a_i];
long_idx = a_i;
}
}
dp.push_back(cur_dp);
dp_idx.push_back(cur_dpidx);
}이렇게 기록을 하면, 최장값을 찾은 후 해당 인덱스에서 순차적으로 돌아가면 문제가 생긴다.
어떤 문제냐면 b_idx를 탐색하는 과정에서, 최장값도 만들어지지만, 후반부의 B 문자를 A에서 검색하는 과정에서
이전 dp와 dp_idx 값이 갱신되는 문제가 생긴다. 이는 dp의 의도한 결과지만, 결과를 역추적하는 경우엔 문제가 발생한다.
따라서, 적절한 long_idx 외에도 b_idx가 주어져있어야 정상적으로 추적이 가능하다.
완성된 코드는 다음과 같다
struct IDX {
int b_idx = -1;
int a_idx = -1;
};
vector<vector<int>> dp(1, vector<int>(A.size()));
vector<vector<IDX>> dp_idx(1, vector<IDX>(A.size()));
for (int b_i = 0; b_i < B.length(); b_i++) {
auto b = B[b_i];
int longest = 0;
int long_idx = -1;
vector<int> cur_dp(A.size());
vector<IDX> cur_dpidx(A.size());
for (int a_i = 0; a_i < A.length(); a_i++) {
auto a = A[a_i];
if (b == a) {
cur_dp[a_i] = longest + 1;
cur_dpidx[a_i] = { b_i, long_idx };
}
else {
cur_dp[a_i] = dp[b_i][a_i];
cur_dpidx[a_i] = dp_idx[b_i][a_i];
}
if (dp[b_i][a_i] > longest) {
longest = dp[b_i][a_i];
long_idx = a_i;
}
}
dp.push_back(cur_dp);
dp_idx.push_back(cur_dpidx);
}
int longest = 0;
int long_idx = -1;
for (int i = 0; i < A.length(); i++) {
if (longest < dp[B.length()][i]) {
longest = dp[B.length()][i];
long_idx = i;
}
}
cout << longest;
if (longest > 0) {
cout << '\n';
IDX cur_idx = { B.length(), long_idx };
stack<char> result;
while (true) {
cur_idx = dp_idx[cur_idx.b_idx][cur_idx.a_idx];
result.push(B[cur_idx.b_idx]);
if (cur_idx.a_idx == -1) break;
}
while (!result.empty()) {
cout << result.top();
result.pop();
}
}역으로 추적은 하지만, 출력은 정방향으로 해야하기 때문에, stack을 사용해서 구현했다.
stringbuilder등을 쓰거나 간단한 메소드를 통해 reverse 하는 방법도 있을 것이다.
사실 알고리즘 문제풀이를 할 때 노래를 듣거나 유튜브를 틀어놓고 문제를 푸는데
이 때문에 집중력의 한계가 생겨 신중하게 생각해야 되는 부분을 비약해서 넘기거나 해결을 못하게 된다
이 부분을 꼭 주의해야겠다.