https://www.acmicpc.net/problem/9252
9252번: LCS 2
LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다.
www.acmicpc.net
들어가며
LCS 문제를 DP로 풀어야한다는 것은 알고 있었지만 길이가 아닌 LCS 문자열을 구하는 과정에서 어려움이 있었습니다. 우선 LCS가 뭔지 간단하게 보고 예제의 결과가 어떻게 나왔는지 과정을 보고 문제 풀이 방식에 대해 설명하겠습니다!
LCS(Longest Common Subsequence)란?
최장 공통 부분 수열이라는 의미로, 주어진 여러 개의 문자열에서 공통으로 부분 문자열이 되는 것 중 가장 길이가 긴 것을 찾는 문제이다.
여기서 포인트는 연속된 문자열이 아니라는 것이다. 그래서 연속된 공통 문자열을 찾는 최장 공통 부분문자열(longest common substring) 문제와 혼동해서는 안된다.
예제를 통해 LCS 문자열 길이를 구하는 과정을 알아보자.
문자열 1. ACAYKP
문자열 2. CAPCAK
우선 초기 값으로 index가 0이 포함된 곳, 즉 행의 첫번째 라인과 열의 첫번째 라인은 0으로 채워준다.
위 그림에서 볼 수 있듯이 1, 2 두가지 경우가 존재한다.
이 경우는 현재 인덱스에서 두 문자열의 문자가 동일한지를 기준으로 판단된다.
1. 두 개의 문자가 다른 경우 (그림에서 1번의 경우 문자열 1의 P와 문자열 2의 A가 비교되는 상황)
이 경우에는 왼쪽과 위쪽의 값 중 최댓값이 현재 위치에 저장된다.
동일한 문자가 아니기 때문에 최장 공통 문자열의 길이를 늘려줄 필요가 없기 때문에 최댓값만 가져와서 업데이트 해준다.
2. 두 개의 문자가 같은 경우 (그림에서 2번의 경우 문자열 1의 A와 문자열 2의 A가 비교되는 상황)
대각선의 값에 +1 한 후에 현재 위치의 값에 추가해준다.
이전 문자열들을 검사해서 구한 최장 공통 문자열의 길이에 +1을 해주게 되는 것이다.
이렇게 마지막 위치까지 반복한 후에 파란색 원의 위치의 값을 결과로 내어주면 모든 문자열을 검사한 후의 최장 공통 문자열 길이가 된다.
DP 점화식을 세워보면,
dp(i, j)는 Xi, Yj의 LCS 길이를 나타낸다.
i, j가 0ㅇ이면 LSC 길이는 0이기 때문에 위에서 0으로 초기화 해준 것이었다.
결론은 같은 문자인 경우 대각선 + 1, 다른 문자이면 왼쪽과 위쪽 중 max 값을 저장되는 것이다.
코드 구현
문자열 길이를 구하는 것까지는 잘 풀어냈지만 LCS 문자열을 구하는 과정이 어려웠다.
1. LCS 문자열 길이 구하기
int len1 = str1.length();
int len2 = str2.length();
dp = new int[len1 + 1][len2 + 1];
for (int i = 1; i <= len1; i++) {
for (int j = 1; j <= len2; j++) {
if (str1.charAt(i - 1) == str2.charAt(j - 1)) {
dp[i][j] = dp[i - 1][j - 1] + 1;
}
else {
dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
}
}
}
우선 점화식을 활용해서 dp 배열의 값을 채워준다. 기본적으로 int 배열에 0으로 저장되니까 이중반복문에서 인덱스 시작 위치를 1로 잡아주었다.
2. LCS 문자열 구하기
방법1. Stack 사용하기
main 메서드에서 이렇게 호출을 한다.
lcsToString(str1, len1, len2);
그럼 아래 메서드가 실행된다. 이때 스택을 사용했는데 만약 동일한 문자여서 대각선 값을 사용한 경우에 스택에 해당 문자를 넣어주어서 dp의 (len1, len2)에서부터 (1, 1)위치까지 검사를 해주는 것이다. 결국 스택에는 LCS 문자열이 들어있게 되는 것이다.
static void lcsToString(String str, int i, int j) {
Stack<Character> st = new Stack<>();
while (i > 0 && j > 0) {
if (dp[i][j] == dp[i-1][j]) i--;
else if (dp[i][j] == dp[i][j-1]) j--;
else {
st.push(str.charAt(i-1));
i--; j--;
}
}
while (!st.empty()) {
sb.append(st.pop());
}
}
전체 코드
public class Main {
static int[][] dp;
static StringBuilder sb = new StringBuilder();
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String str1 = br.readLine();
String str2 = br.readLine();
int len1 = str1.length();
int len2 = str2.length();
dp = new int[len1 + 1][len2 + 1];
for (int i = 1; i <= len1; i++) {
for (int j = 1; j <= len2; j++) {
if (str1.charAt(i - 1) == str2.charAt(j - 1)) {
dp[i][j] = dp[i - 1][j - 1] + 1;
}
else {
dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
}
}
}
sb.append(dp[len1][len2]).append("\n");
lcsToString(str1, len1, len2);
System.out.println(sb);
}
static void lcsToString(String str, int i, int j) {
Stack<Character> st = new Stack<>();
while (i > 0 && j > 0) {
if (dp[i][j] == dp[i-1][j]) i--;
else if (dp[i][j] == dp[i][j-1]) j--;
else {
st.push(str.charAt(i-1));
i--; j--;
}
}
while (!st.empty()) {
sb.append(st.pop());
}
}
}
그런데 나는 이걸 StringBuilder를 사용해서 풀 수 있을 거라고 생각했다.
굳이 스택에 넣고 빼지 않아도 된다고 생각해서 아래와 같이 해결했다.
static void lcsToString(String str, int i, int j) {
StringBuilder tmp = new StringBuilder();
while (i > 0 && j > 0) {
if (dp[i][j] == dp[i-1][j]) i--;
else if (dp[i][j] == dp[i][j-1]) j--;
else {
tmp.append(str.charAt(i-1));
i--; j--;
}
}
sb.append(tmp.reverse());
}
뒤에서부터 검사를 하기 때문에 찾은 LCS 문자를 reverse 해주면 결과를 구할 수 있다. 제출 결과를 비교해보면 StringBuilder 사용한 것이 조금 더 효율적이었다.
전체 코드
public class Main {
static int[][] dp;
static StringBuilder sb = new StringBuilder();
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String str1 = br.readLine();
String str2 = br.readLine();
int len1 = str1.length();
int len2 = str2.length();
dp = new int[len1 + 1][len2 + 1];
for (int i = 1; i <= len1; i++) {
for (int j = 1; j <= len2; j++) {
if (str1.charAt(i - 1) == str2.charAt(j - 1)) {
dp[i][j] = dp[i - 1][j - 1] + 1;
}
else {
dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
}
}
}
sb.append(dp[len1][len2]).append("\n");
lcsToString(str1, len1, len2);
System.out.println(sb);
}
static void lcsToString(String str, int i, int j) {
StringBuilder tmp = new StringBuilder();
while (i > 0 && j > 0) {
if (dp[i][j] == dp[i-1][j]) i--;
else if (dp[i][j] == dp[i][j-1]) j--;
else {
tmp.append(str.charAt(i-1));
i--; j--;
}
}
sb.append(tmp.reverse());
}
}
댓글