https://www.acmicpc.net/problem/9252
소요 시간: 20분
메모리: 16048KB
시간: 96ms
🔥 문제
LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다.
입력
첫째 줄과 둘째 줄에 두 문자열이 주어진다. 문자열은 알파벳 대문자로만 이루어져 있으며, 최대 1000글자로 이루어져 있다.
출력
첫째 줄에 입력으로 주어진 두 문자열의 LCS의 길이를, 둘째 줄에 LCS를 출력한다.
LCS가 여러 가지인 경우에는 아무거나 출력하고, LCS의 길이가 0인 경우에는 둘째 줄을 출력하지 않는다.
🍀 풀이
BOJ.9251 LCS 문제를 풀이하면서 LCS에 대해 알아본 적이 있다.
저번 문제는 LCS의 길이를 출력하는 문제였다면, 이번은 LCS의 길이와 함께 LCS를 출력해야하는 문제이다.
LCS의 길이는 저번에 풀이를 했으니 LCS를 출력하는 방법에 대해서 풀이를 하려고 한다.
LCS를 구하는 식을 보자면..
두 문자(A[a]와 B[b])가 같은 경우, lcs[a+1][b+1] = lcs[a][b]+1이고
두 문자가 다른 경우, lcs[a+1][b+1] = Math.max(lcs[a][b+1], lcs[a+1][b])였다.
두 문자가 같은 경우 lcs[a][b] 값에서 1을 더하기 때문에 lcs[a+1][b+1]값이 lcs[a][b+1]과 lcs[a+1][b] 값보다 크다는 것을 알 수 있다.
두 문자가 다른 경우는 lcs[a+1][b+1]값이 lcs[a][b+1]과 lcs[a+1][b] 중 큰 값이 들어 있을 것이다.
LCS를 구하기 위해서 거꾸로 올라가는 것을 선택했다.
lcs[a][b]가 lcs[a-1][b]과 lcs[a][b-1] 중 하나와 같은 경우는 A[a-1]와 B[b-1] 문자는 같지 않다는 의미이다. 그러므로 lcs[a-1][b]과 lcs[a][b-1] 중 같은 곳으로 이동한다.("LCS가 여러 가지인 경우에는 아무거나 출력"이라는 조건이 있으므로 어디를 가도 상관없다.)
lcs[a][b]가 lcs[a-1][b]과 lcs[a][b-1] 모두 다른 경우는 A[a-1]와 B[b-1] 문자가 같다는 의미이다. 그러므로 A[a-1]를 StringBuilder객체 sb에 저장하고 lcs[a-1][b-1]로 이동한다.
그리고 이동한 곳이 0인 경우 LCS를 모두 찾았으므로 찾기를 종료하고, sb를 반대로 뒤집어서 출력한다.
1. 문자열 A와 B를 입력받고, 문자 배열로 저장한다.
2. int형 2차원 배열 lcs_arr를 정의한다.
3. 문자열 B와 문자열 A를 2중 for문을 사용하여 모든 문자끼리 비교할 수 있도록 한다.
1. A[a-1]와 B[b-1]의 문자가 같은 경우, lcs_arr[a-1][b-1]에 1을 더한 값을 lcs_arr[a][b]에 저장한다.
2. A[a-1]와 B[b-1]의 문자가 다른 경우, lcs_arr[a-1][b]과 lcs_arr[a][b-1] 중 더 큰 값을 lcs_arr[a][b]에 저장한다.
4. StringBuilder 객체 sb를 생성하고, a에 A.length, b에 B.length를 저장한다.
5. lcs_arr[a][b]가 0보다 크다면 반복한다.
1. lcs_arr[a][b]와 lcs_arr[a][b-1]가 같은 경우, lcs_arr[a][b-1]로 이동하기 위해 b를 1 줄인다.
2. lcs_arr[a][b]와 lcs_arr[a-1][b]가 같은 경우, lcs_arr[a-1][b]로 이동하기 위해 a를 1 줄인다.
3. 위 두 경우가 아니라면, A[a-1]과 B[b-1]은 같은 문자라는 의미로 sb에 A[a-1]을 저장하고, a와 b를 1씩 줄인다.
6. sb를 뒤집어서 LCS를 만든다.
7. LCS 길이인 lcs_arr[A.length][B.length]와 LCS 중 하나인 sb를 출력한다.
💻 전체 코드
import java.io.BufferedReader;
import java.io.InputStreamReader;
public class LCS2_9252 {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
char[] A = br.readLine().trim().toCharArray();
char[] B = br.readLine().trim().toCharArray();
int[][] lcs_arr = new int[A.length + 1][B.length + 1];
for (int a = 1; a <= A.length; a++) {
for (int b = 1; b <= B.length; b++) {
if (A[a - 1] == B[b - 1]) {
lcs_arr[a][b] = lcs_arr[a - 1][b - 1] + 1;
} else if (lcs_arr[a][b - 1] < lcs_arr[a - 1][b]) {
lcs_arr[a][b] = lcs_arr[a - 1][b];
} else {
lcs_arr[a][b] = lcs_arr[a][b - 1];
}
}
}
StringBuilder sb = new StringBuilder();
int a = A.length;
int b = B.length;
while (0 < lcs_arr[a][b]) {
if (lcs_arr[a][b] == lcs_arr[a][b - 1]) {
b--;
} else if (lcs_arr[a][b] == lcs_arr[a - 1][b]) {
a--;
} else {
sb.append(A[--a]);
b--;
}
}
System.out.println(lcs_arr[A.length][B.length]);
System.out.print(sb.reverse());
}
}💫 리뷰
lcs 까먹지말자~~
'algorithm' 카테고리의 다른 글
| [BOJ] 백준 9251번 LCS (Java) (1) | 2024.10.29 |
|---|---|
| [BOJ] 백준 1261번 알고스팟 (Java) (0) | 2024.05.17 |
| [BOJ] 백준 3078번 좋은 친구 (Java) (0) | 2024.05.08 |
| [BOJ] 백준 1655번 가운데를 말해요 (Java) (0) | 2024.05.03 |
| [BOJ] 백준 17244번 아맞다우산 (Java) (2) | 2024.05.02 |
