[백준 / BOJ] C++ 9252 LCS 2

9252번: LCS 2

 

문제

https://www.acmicpc.net/problem/9252

9252번: LCS 2

 

 

풀이

9251번 LCS의 확장 버전이다. LCS의 길이를 구하는 풀이는 아래 링크를 참고하길 바란다.

 https://khyunx.tistory.com/57

[백준 / BOJ] C++ 9251 LCS

 

위 문제에서 추가된 점은 LCS 자체를 구해야 한다. 길이를 구하는 코드에서 길이가 아닌 문자열로 바꿔주었고 문자열의 길이를 비교해 가며 같은 방식을 진행했다. 이렇게 하니 시간초과를 받았다. 

 

이유는 두 문자열의 길이가 N이라고 했을 때, 시간 복잡도가 O(N^2)일 줄 알았는데 문자열로 하게 되면 문자열끼리 비교할 때 또 시간이 걸려 O(N^3)이 되기 때문이다.

 

아래는 시간초과 코드다.

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

int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  string a, b;
  cin >> a >> b;
  int a_length = a.length();
  int b_length = b.length();
  vector<vector<string>> dp(a_length + 1, vector<string>(b_length + 1, ""));
  for (int i = 1; i <= a_length; i++)
    for (int j = 1; j <= b_length; j++)
      if (a[i - 1] == b[j - 1]) {
        dp[i][j] = dp[i - 1][j - 1] + a[i - 1];
      } else {
        if (dp[i - 1][j].length() > dp[i][j - 1].length())
          dp[i][j] = dp[i - 1][j];
        else
          dp[i][j] = dp[i][j - 1];
      }
  cout << dp[a_length][b_length].length() << '\n'
       << dp[a_length][b_length];
  return 0;
}

 

정답 AC를 받은 풀이는 9251번 문제와 같이 한 다음 가장 오른쪽 아래부터 역추적을 통해 정답을 찾아내는 방법이다. 표와 함께 설명하겠다.

	0	A	C	A	Y	K	P
0	0	0	0	0	0	0	0
C	0	0	1	1	1	1	1
A	0	1	1	2	2	2	2
P	0	1	1	2	2	2	3
C	0	1	2	2	2	2	3
A	0	1	2	3	3	3	3
K	0	1	2	3	3	4	4

가장 오른쪽 아래에서 LCS의 길이가 4임을 알 수 있다. 여기서 왼쪽과 위쪽을 비교해 LCS의 길이가 같은지 비교한다.

1. 만약 같으면, 그쪽으로 이동한다. (왼, 위 모두 같을 시 왼쪽 우선)
2. 둘 다 다르면, 그 위치의 문자가 가장 LCS의 한 글자며 왼쪽 대각선 위로 이동한다.

위 방법을 거친 경로를 빨간색으로 표시하면 아래와 같다.

	0	A	C	A	Y	K	P
0	0	0	0	0	0	0	0
C	0	0	1	1	1	1	1
A	0	1	1	2	2	2	2
P	0	1	1	2	2	2	3
C	0	1	2	2	2	2	3
A	0	1	2	3	3	3	3
K	0	1	2	3	3	4	4

두꺼운 부분은 그 위치의 문자가 LCS를 이룬다.

 

 

코드

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

int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  string a, b;
  cin >> a >> b;
  int a_size = a.size();
  int b_size = b.size();
  vector<vector<int>> dp(a_size + 1, vector<int>(b_size + 1, 0));
  // LCS 길이 구하기
  for (int i = 1; i <= a_size; i++)
    for (int j = 1; j <= b_size; j++)
      if (a[i - 1] == b[j - 1])
        dp[i][j] = dp[i - 1][j - 1] + 1;
      else
        dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
  int len = dp[a_size][b_size];
  cout << len << '\n';
  // LCS 구하기
  vector<char> LCS(len, ' ');
  int x = a_size, y = b_size; // dp 배열에서 탐색을 시작할 좌표
  while (len > 0) { // 역추적하며 모든 문자를 찾을 때까지
    if (dp[x - 1][y] == len) { // 왼쪽이 같은 길이일 때 x좌표 이동
      x--;
    } else if (dp[x][y - 1] == len) { // 왼쪽은 같은 길이가 아니면서 위쪽이 같을 때 y좌표 이동
      y--;
    } else { // 둘 다 아닐 때 그 위치의 문자를 배열에 추가, 대각선으로 이동
      LCS[len - 1] = a[x - 1];
      x--;
      y--;
      len--;
    }
  }
  for (char i : LCS)
    cout << i;
  return 0;
}