백준 9252번: LCS 2

문제

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

9252번: LCS 2

---

풀이

9251번 문제를 응용한 문제로 LCS(Longest Common Subsequence, 최장 공통 부분 수열)를, 즉 문자로 된 두 수열이 주어졌을 때 모두의 부분 수열이 되는 수열 중 가장 긴 것을 구하는 문제입니다.

예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 됩니다.

---

코드

C언어

바텀업 방식을 이용한 코드입니다.

dp 배열은 9251번 문제에서와 동일하며 임의의 수 x, y가 있을 때 str1[0부터 x까지]와 str2[0부터 y까지]가 조건에 맞춰 가질 수 있는 가장 긴 부분 수열의 길이를 dp[x + 1][y + 1]에 저장합니다.

이후 i와 j를 포함한 이중 for문을 실행하여 str1[i - 1]과 str2[j - 1]이 같다면 dp[i - 1][i - 1]에 1을 더해준 값을, 다르다면 dp[i - 1][j]와 dp[i][j - 1] 중 큰 값을 dp[x][y] 값에 넣어줍니다.

모든 입력이 끝나면 x가 strlen(str1)이고 y가 strlen(str2), 즉 각 문자열의 끝부분 + 1이라고 할 때 dp[x][y]을 출력하고 해당 부분 수열을 출력하기 위해 스택과 while문을 사용하는데 dp[x][y]와 dp[x - 1][y]가 같다면 x에서 1을 빼주고 dp[x][y - 1]와 같다면 y에서 1을 빼주고 둘 다 다르다면 스택에 해당 문자를 스택에 넣어주고 x와 y에서 1을 빼줍니다.

모든 비교가 끝나고 스택에 모든 값이 들어갔다면 스택의 모든 값을 문제 조건에 맞게 출력합니다.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define math_max(a, b) a > b ? a : b
char* stack;
int stackIdx = -1;
void push(char value) {
	stack[++stackIdx] = value;
}
int is_empty() {
	if (stackIdx < 0) return 1;
	else return 0;
}
char pop() {
	return stack[stackIdx--];
}
main() {
	char str1[1001], str2[1001];
	scanf("%s %s", str1, str2);
	int x = strlen(str1), y = strlen(str2);
	int** dp = (int**)malloc(sizeof(int*) * (x + 1));
	for (int i = 0; i <= x; i++) {
		dp[i] = (int*)malloc(sizeof(int) * (y + 1));
		for (int j = 0; j <= y; j++) {
			dp[i][j] = 0;
		}
	}
	for(int i = 1; i <= x; i++) {
		for (int j = 1; j <= y; j++) {
			if (str1[i - 1] == str2[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]);
			}
		}
	}
	printf("%d\n", dp[x][y]);
	stack = (char*)malloc(sizeof(char) * dp[x][y]);
	while (x > 0 && y > 0) {
		if (dp[x][y] == dp[x - 1][y]) x--;
		else if (dp[x][y] == dp[x][y - 1]) y--;
		else {
			push(str1[x - 1]);
			x--;
			y--;
		}
	}
	while (!is_empty()) {
		printf("%c", pop());
	}
}

자바

탑다운 방식을 이용한 코드입니다.

dp 배열은 지금까지 사용한 것들과 다르게 임의의 수 x, y가 있을 때 str1.charAt(0부터 x까지)와 str2.charAt(0부터 y까지)가 조건에 맞춰 가질 수 있는 가장 긴 부분 수열을 의미합니다.

LCS 함수에서 dp[x][y]가 null이라면 str1.charAt(x)와 str2.charAt(y)를 비교합니다. 만약 같다면 LIS(x - 1, y - 1)을 통해 dp[x - 1][y - 1]을 받아 해당 문자를 더해준 문자열을 dp[x][y] 값에 넣어주고 다르다면 LCS(x - 1, y)와 LCS(x, y - 1)을 통해 dp[x - 1][y]와 dp[x][y - 1] 중 길이가 더 긴 값을 넣어준 뒤에 그 값을 반환합니다.

모든 입력이 끝나면 x가 str1.length() - 1이고 y가 str2.length() - 1, 즉 각 문자열의 끝부분이라고 할 때 LCS(x, y)을 실행하여 가장 긴 부분 수열을 받고 Stringbuilder에 해당 문자열의 길이와 문자열을 넣어 한꺼번에 출력합니다.

import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {

    static String str1, str2;
    static String[][] dp;

    static String LCS(int x, int y) {
        if (x == -1 || y == -1) return "";
        if (dp[x][y] == null) {
            if (str1.charAt(x) == str2.charAt(y)) {
                dp[x][y] = LCS(x - 1, y - 1) + str1.charAt(x);
            } else {
                String L = LCS(x - 1, y), R = LCS(x, y - 1);
                dp[x][y] = L.length() > R.length() ? L : R;
            }
        }
        return dp[x][y];
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        str1 = br.readLine();
        str2 = br.readLine();
        dp = new String[str1.length()][str2.length()];
        int x = str1.length() - 1, y = str2.length() - 1;
        String str = LCS(x, y);
        StringBuilder sb = new StringBuilder();
        sb.append(str.length()).append("\n").append(str);
        System.out.println(sb);
    }
}

 

---

결론

자바로 탑다운 방식을 이용한 코드에서  9251번 문제에서 작성한 LCS 함수를 그대로 사용한다면 틀렸거나 런타임 에러가 발생하는데 왜 그런지는 더 생각해봐야 할 것 같습니다.