
https://www.acmicpc.net/problem/9252
두 문자열 간의 최장 공통 부분 수열(Longest Common Subsequence, LCS)을 구하는 문제다. LCS는 두 문자열에서 순서를 유지하면서 삭제 가능한 가장 긴 공통 부분 문자열을 의미한다.
이를 동적 계획법(DP)을 사용하여 효율적으로 계산하고자 했다.
먼저 두 문자열 s1과 s2를 입력받고, 두 문자열의 길이를 기반으로 DP 배열을 초기화한다.
dp[i][j]는 문자열 s1의 첫 i글자와 s2의 첫 j글자 간의 최장 공통 부분 수열의 길이를 저장한다.
DP 테이블을 채우는 과정에서,
현재 문자 s1.charAt(i - 1)와 s2.charAt(j - 1)이 같으면
dp[i][j]는 dp[i - 1][j - 1] + 1로 갱신된다.
문자가 다르면, 이전 단계의 값 중 더 큰 값을 가져온다
(즉, dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1])).
DP 테이블이 완성된 후, dp[s1.length()][s2.length()]에는
최장 공통 부분 수열의 길이가 저장된다.
이를 출력한 뒤, 실제 공통 부분 수열을 추출한다.
이를 위해 문자열의 끝에서부터 DP 테이블을 역추적하며
공통된 문자를 찾아 StringBuilder에 추가한다.
공통된 문자는 테이블 값이 증가한 경우에 해당하며,
이 과정을 반복하여 LCS를 역순으로 저장한 후,
최종적으로 뒤집어 올바른 순서로 출력한다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class b9252 {
static String s1, s2;
static int[][] dp;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
s1 = br.readLine();
s2 = br.readLine();
int s1Size = s1.length();
int s2Size = s2.length();
dp = new int[s1Size + 1][s2Size + 1];
for (int i = 1; i <= s1Size; i++) {
for (int j = 1; j <= s2Size; j++) {
if (s1.charAt(i - 1) == s2.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]);
}
}
}
System.out.println(dp[s1Size][s2Size]);
StringBuilder sb = new StringBuilder();
int i = s1Size, j = s2Size;
while (i > 0 && j > 0) {
if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
sb.append(s1.charAt(i - 1));
i--;
j--;
} else if (dp[i - 1][j] > dp[i][j - 1]) {
i--;
} else {
j--;
}
}
System.out.println(sb.reverse());
}
}
'Algorithm & Data Structures > BOJ' 카테고리의 다른 글
Lv 2. 이모티콘 할인행사 (0) | 2025.01.01 |
---|---|
b9466. 텀 프로젝트 (0) | 2024.12.31 |
b7579. 앱 (0) | 2024.12.26 |
b7453. 합이 0인 네정수 (1) | 2024.12.20 |
b2623. 음악프로그램 (0) | 2024.12.17 |