https://www.acmicpc.net/problem/9252
문제 요약
대문자로 이루어진 두 문자열 수열이 주어질 때, 최장 공통 부분 수열(LCS)을 얻어라.
여기서 LCS는 두 수열 모두에서 부분 수열에 되는 수열 중 가장 긴 것을 의미한다.
결과는 LCS의 길이와 그 LCS의 값을 출력해야 한다.
다만 여러 경우의 LCS가 존재한다면 그 중 하나를 아무거나 출력하며, LCS의 길이가 0이라면 LCS를 출력하지 않는다.
문제 접근
LCS의 길이 얻기
LCS의 길이를 구하는 문제는 DP(Dynamic Programming)를 이용해서 해결할 수 있다.
기본적인 접근은 두 문자열의 각 문자를 나타내는 2차원 배열을 생성한 뒤, 문자가 일치하는 곳에서 1을 더해가며 두 문자열의 문자를 훑는 것이다.
이야기를 이해하기 위해 예시 배열을 만들어보자.
C A P C A K
A 0 1 0 0 1 0
C 1 0 0 1 0 0
A 0 1 0 0 1 0
Y 0 0 0 0 0 0
K 0 0 0 0 0 1
P 0 0 1 0 0 0위의 배열은 각 문자열의 문자가 서로 일치한 경우 1, 아니라면 0을 얻는 형태이다. 이러한 배열을 직접 문제 해결에 사용하지는 않지만, 이해를 위해 그려보았다.
실제 문제에서는 LCS의 길이를 누적하면서 배열의 값을 얻는다. 이때 두 문자가 일치하는 경우와 일치하지 않는 경우에는 진행 방식이 다르다.
- 두 문자가 일치하는 경우, 왼쪽 위 대각선 값에 1을 더한 값을 얻는다.
- 두 문자가 일치하지 않는 경우, 왼쪽 또는 위의 값 중에서 더 큰 값을 그대로 가져온다.
일치하는 경우에 (왼쪽 위 값 + 1)로 값을 얻는 이유는, 오른쪽이나 아래로 진행하며 하나의 문자가 여러 번 일치한다고 판정되는 경우를 방지하기 위함이다.
이러한 규칙을 진행하면 다음과 같은 LCS 배열을 얻을 수 있다.
C A P C A K
A 0 1 1 1 1 1
C 1 1 1 2 2 2
A 1 2 2 2 3 3
Y 1 2 2 2 3 3
K 1 2 2 2 3 4
P 1 2 3 3 3 4최종적으로 두 문자열을 모두 고려한 오른쪽 아래의 값이 가능한 LCS의 최대 길이가 되며, 정답과 일치함을 확인할 수 있다.
LCS 얻기
다만 문제는 LCS의 길이 뿐만 아니라 LCS 그 자체의 값도 얻어야 한다는 것이다.
이 문제는 직전 경로를 기록하는 배열을 추가로 만들어서 해결할 수 있다.
앞서 LCS 길이 배열은 왼쪽, 위, 왼쪽 위 셋 중 하나에서 오는 것을 알 수 있으며, 특히 두 문자가 일치하는 경우에는 반드시 왼쪽 위에서 온다.
따라서 길이 배열을 얻으며 오는 방향 배열을 함께 기록하고, 배열 완성 후 오른쪽 아래 인덱스에서 경로를 따라가며 LCS를 얻을 수 있다.
왼쪽 위에서 오는 경우(두 문자가 일치하는 경우)에만 LCS에 문자를 추가하면 된다.
예시로 오는 방향 배열을 나타내면 다음과 같다. 이때 0은 왼쪽, 1은 위, 2는 왼쪽 위를 나타낸다고 하자.
C A P C A K
A 0 2 0 0 2 0
C 2 0 0 2 0 0
A 1 2 0 0 2 0
Y 1 0 0 0 1 0
K 1 0 0 0 0 2
P 1 0 2 0 0 1마지막 인덱스에서 따라가면, 위 → 왼쪽 위(K) → 위 → 왼쪽 위(A) → 왼쪽 위(C) → 왼쪽 → 왼쪽 위(A)으로 진행됨을 알 수 있다.
순서대로 문자를 추가하면 KACA를 얻는데, 이를 뒤집은 ACAK가 LCS이다.
여기서는 왼쪽과 위의 값이 같은 경우에 왼쪽으로 이동하도록 설정했는데(뒤의 풀이와 동일), 어디로 이동하든 결국 같은 길이의 LCS를 얻는다.
풀이
기본적인 아이디어는 다음과 같다.
- LCS 길이 배열과 오는 방향 배열을 선언한다.
- 인덱스(문자)를 순서대로 훑으며 일치하는 경우에는 (왼쪽 위 값 + 1), 일치하지 않는 경우에는 (왼쪽 값) 또는 (위 값) 중에 더 큰 값을 그대로 얻어 LCS 길이 배열을 채운다.
- 이와 동시에 왼쪽, 위, 왼쪽 위의 오는 방향 배열을 기록한다.
- 두 배열을 모두 채우면 LCS 길이 배열로 LCS의 길이를 얻을 수 있다.
- LCS의 길이가 0이 아니라면 방향 배열을 따라가며 문자를 순서대로 추가하고, 마지막에 이를 뒤집어 LCS를 얻는다.
배열 관리의 편의를 위해서 각 문자열의 인덱스는 1부터 시작한다. 인덱스 0은 모두 0의 값으로 비워둔다.
이를 구현한 코드는 다음과 같다.
import java.util.*;
import java.io.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
// 두 문자열 입력 받기
String strA = br.readLine();
String strB = br.readLine();
int sizeA = strA.length();
int sizeB = strB.length();
// 두 문자열의 각 문자를 비교하기 위한 배열 구성(세로: 문자열 A, 가로: 문자열 B)
int[][] lenLCS = new int[sizeA+1][sizeB+1]; // LCS 길이
int[][] fromWhere = new int[sizeA+1][sizeB+1]; // 온 방향
// 배열을 모두 0으로 초기화
for (int i = 0; i < sizeA+1; i++) {
for (int j = 0; j < sizeB+1; j++) {
lenLCS[i][j] = 0;
fromWhere[i][j] = 0;
}
}
// 배열을 채운다.
// 온 방향은 왼쪽에서 오면 FROM_LEFT, 위에서 오면 FROM_UP로 설정, 대각선에서 오면 FROM_UPLEFT로 설정
// 문자열이 일치하면 대각선에서 오며, 다르다면 왼쪽이나 위 중 최대값인 곳에서 온다. (같다면 상관없음)
final int FROM_LEFT = 0;
final int FROM_UP = 1;
final int FROM_UPLEFT = 2;
// 구현의 편의를 위해 i, j가 1부터 시작하기 때문에 charAt(i-1), charAt(j-1) 이렇게 사용해야 한다.
for (int i = 1; i < sizeA+1; i++) {
for (int j = 1; j < sizeB+1; j++) {
// 문자가 일치하는 경우
if (strA.charAt(i-1) == strB.charAt(j-1)) {
lenLCS[i][j] = lenLCS[i-1][j-1] + 1;
fromWhere[i][j] = FROM_UPLEFT;
}
// 일치하지 않는 경우
else {
// 위가 왼쪽보다 큰 경우
if (lenLCS[i-1][j] > lenLCS[i][j-1]) {
lenLCS[i][j] = lenLCS[i-1][j];
fromWhere[i][j] = FROM_UP;
}
// 왼쪽이 더 크거나 같은 경우
else {
lenLCS[i][j] = lenLCS[i][j-1];
fromWhere[i][j] = FROM_LEFT;
}
}
}
}
// LCS의 길이를 얻는다.
int longest = lenLCS[sizeA][sizeB];
// 마지막 위치에서 시작해 처음으로 돌아가며 문자열을 구성(온 방향보다 해당 위치 값이 크면 해당 위치 문자 추가)
// LCS의 길이가 0이라면 수행할 필요 없다.
if (longest > 0) {
int nowX = sizeB;
int nowY = sizeA;
while (true) {
// 둘 중 하나라도 0이 되면 끝남(범위를 벗어난 것)
if (nowX == 0 || nowY == 0) break;
// 이전 경로로 돌아간다
// 위에서 온 경우
if (fromWhere[nowY][nowX] == FROM_UP) {
nowY--;
}
// 왼쪽에서 온 경우
else if (fromWhere[nowY][nowX] == FROM_LEFT){
nowX--;
}
// 왼쪽 위 대각선에서 온 경우 - 문자가 같은 것이므로 추가해줌
else {
sb.append(strA.charAt(nowY-1)); // 인덱스-1로 사용해야 한다는 점 기억
nowX--;
nowY--;
}
}
}
// 앞서 구한 문자열을 뒤집어야 LCS가 된다
sb.reverse();
// 정답 출력
if (longest == 0) System.out.println(0);
else {
System.out.println(longest);
System.out.println(sb);
}
}
}회고
틀렸던 이유 1
두 문자가 일치하는 경우에도 왼쪽이나 위에서 올 수 있다고 생각했다. 하지만 그렇게 하면 하나의 문자가 다른 문자열의 같은 문자와 계속 같다고 계산되어 누적되기 때문에 틀린 결과를 얻게 된다.
문자가 일치하는 경우에는 왼쪽 위에서 와야 한다.
틀렸던 이유 2
테스트 코드를 지우지 않았다.... 이것도 자주 일어날 수 있는 실수니 유의하기.
