[9252] LCS 2

✔ LCS 2

[백준 9252]

문제 분석하기

LCS는 문자열을 이용한 대표적인 동적 계획법 문제이므로 각 문자열을 축으로 하는 2차원 배열을 생성하여 점화식 배열로 사용하며

각 위치 인덱스를 마지막 문자로 하는 두 문자열의 최장 공통 수열의 길이를 저장

손으로 풀어보기

1. 점화식의 형태와 의미를 도출
   • D[i][j]는 각 위치 인덱스를 마지막 문자로 하는 두 문자열의 최장 공통 수열의 길이
2. 점화식을 구함
   • 특정 자리가 가리키는 행과 열의 문자열 값을 비교해 값이 같으면 배열의 대각선 왼쪽 위의 값에 1을 더한 값을 저장
     D[i][j] = D[i - 1][j - 1] + 1
   • 특정 자리가 가리키는 행과 열의 문자열 값을 비교해 값이 다르면 배열의 왼쪽의 값 중 큰 값을 선택해 저장
     D[i][j] = Math.max(D[i - 1][j], D[i][j - 1])
3. 점화식으로 D 배열을 채운 후 LCS 정답을 출력
   • 먼저 마지막부터 탐색을 수행
   • 해당 자리에 있는 인덱스 문자열 값을 비교해 값이 같으면
     최장 증가 수열에 해당하는 문자로 기록하고, 왼쪽 대각선으로 이동
   • 비교한 값이 다르면 왼쪽 위의 값 중 큰 값으로 이동

예) ACAYKP, CAPCAK의 LCS는 ACAK

1) 4 → K ≠ P이므로 왼쪽 위의 값 중 큰 값으로 이동

2) 4 → K  = K이므로 최장 증가 수열에 해당하는 문자로 기록하고, 왼쪽 대각선으로 이동

3) 3 → A ≠ Y이므로 왼쪽 위의 값 중 큰 값으로 이동

4) 3 → A  = A이므로 최장 증가 수열에 해당하는 문자로 기록하고, 왼쪽 대각선으로 이동

5) 2 → C  = C이므로 최장 증가 수열에 해당하는 문자로 기록하고, 왼쪽 대각선으로 이동

6) 1 → P ≠ A이므로 왼쪽 위의 값 중 큰 값으로 이동

5) 1 → A  = A이므로 최장 증가 수열에 해당하는 문자로 기록

	A	C	A	Y	K	P
C	0	1	1	1	1	1
A	1	1	2	2	2	2
P	1	1	2	2	2	3
C	1	2	2	2	2	3
A	1	2	3	3	3	3
K	1	2	3	3	4	4

슈도코드 작성하기

D(2차원 점화식 배열) A(1번째 문자열) B(2번째 문자열)
Path(LCS 저장하기 리스트)
for(i -> 1 ~ A 문자열 길이) {
    for(j -> 1 ~ B 문자열 길이) {
        A[i]와 B[i]가 같으면 D[i][j]의 값을 왼쪽 대각선값 + 1로 저장하기
        다른 경우에는 왼쪽의 값과 위의 값 중 큰 값으로 D[i][j] 채우기
    }
}
D의 마지막 값을 출력하기(LCS 길이)
getText 함수를 이용해 LCS 문자열 출력하기
getText(row, column) {
    A[row]와 B[column]가 같으면 LCS에 기록, 대각선 왼쪽 위로 이동
    다른 경우 왼쪽 값과 위의 값 중 값이 더 큰 쪽으로 이동하기
}

코드 구현하기

/**
 * 9252) LCS_2
 */
public class D090_9252 {
    static long[][] D;
    static ArrayList<Character> Path;
    static char[] A;
    static char[] B;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        // A(1번째 문자열)
        A = br.readLine().toCharArray();
        // B(2번째 문자열)
        B = br.readLine().toCharArray();
        // D(각 위치 인덱스를 마지막 문자로 하는 두 문자열의 최장 공통 수열의 길이를 나타내는 2차원 점화식 배열)
        D = new long[A.length + 1][B.length + 1];
        // Path(LCS 저장하기 리스트)
        Path = new ArrayList<Character>();
        for (int i = 1; i <= A.length; i++) {
            for (int j = 1; j <= B.length; j++) {
                // A[i]와 B[i]가 같으면 D[i][j]의 값을 왼쪽 대각선값 + 1로 저장하기
                if (A[i - 1] == B[j - 1]) {
                    D[i][j] = D[i - 1][j - 1] + 1;
                }
                // 다른 경우에는 왼쪽의 값과 위의 값 중 큰 값으로 D[i][j] 채우기
                else {
                    D[i][j] = Math.max(D[i - 1][j], D[i][j - 1]);
                }
            }
        }
        // D의 마지막 값을 출력하기(LCS 길이)
        System.out.println(D[A.length][B.length]);
        // getText 함수를 이용해 LCS 문자열 출력하기
        getText(A.length, B.length);
        for (int i = Path.size() - 1; i >= 0; i--) {
            System.out.print(Path.get(i));
        }
        System.out.println();
    }

    // LCS 출력하기 함수
    private static void getText(int row, int column) {
        if (row == 0 || column == 0)
            return;
        // A[row]와 B[column]가 같으면
        if (A[row - 1] == B[column - 1]) {
            // LCS에 기록
            Path.add(A[row - 1]);
            // 대각선 왼쪽 위로 이동
            getText(row - 1, column - 1);
        }
        // 다른 경우
        else {
            // 왼쪽 값과 위의 값 중 값이 더 큰 쪽으로 이동하기
            if (D[row - 1][column] > D[row][column - 1])
                getText(row - 1, column);
            else
                getText(row, column - 1);
        }
    }
}