[백준] 9252 : LCS 2 (JAVA)

난이도

🥇 4

 

링크

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

9252번: LCS 2

---

문제

---

풀이과정

해당 문제는 최장 공통 부분수열 (LCS)를 사용하는 문제이다.

LCS란 Longest Common Subsequence의 약자로, 최장 공통 문자열 (Longest Common Substring)을 말하기도 한다.

 

문자열 ABCDEF 와 GBCDFE로 차이점을 알아보자면 

최장 공통 부분수열 : ABCDEF 와 GBCDFE ➡️ BCDF / ABCDEF 와 GBCDFE ➡️ BCDE 2가지가 될 수 있고,

최장 공통 문자열 :  ABCDEF와GBCDFE ➡️BCD 가 될 수 있다.

 

즉, 최장 공통 문자열은 부분 문자열이 아니기 때문에 한번에 이어져있는 문자열만 가능하다는 것이다!

 

 하지만, 이번 문제는 최장 공통 문자열이 아닌! 최장 공통 부분수열을 사용하여 푸는 문제였다.

 

우선 예제에서 주어진 두 수열은 ACAYKP와 CAPCAK 이다.

두 수열에서 LCS를 2차원 배열을 사용하여 구해보자면, 배열 안의 수는 LCS의 길이이다.

 

만약 두 문자가 같다면 왼쪽 위 대각선의 값에 +1을 해주고,

dp[i][j] = dp[i-1][j-1] + 1;

두 문자가 다르다면 왼쪽이나 위쪽 값 중 큰 값에 +1을 해준다.

dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);

 

위의 점화식을 통해 구한 배열이다.

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

 

이때 색칠된 숫자는 dp의 값이 변하는 부분인 것을 확인할 수 있다.

그렇기에 기존 LCS에서 최장 공통 부분수열을 구하려면 해당 위치들을 탐색하여 출력하면 되는 것이다.

 

즉, 위의 점화식을 반대로 만들면 되기에 

1. 현재 값 == 위쪽 값  ➡️ 위쪽으로 이동

2. 현재 값 == 왼쪽 값 ➡️ 왼쪽으로 이동

3. 1과 2 모두 아니라면 ➡️ 왼쪽 위 대각선에서 온 값  ➡️ 두 문자 같음 ➡️ Stack에 넣기 ➡️ 왼쪽 위 대각선으로 이동

 

위와 같은 과정을 거친 후 Stack에 입력된 값을 pop하여 출력하면 최장 공통 부분수열인 ACAK를 구할 수 있다.

 

📌 Stack을 사용한 이유? 후입선출의 자료구조로 뒤에서부터 탐색하였기 때문에 문자열을 순차적으로 출력하기 위해 사용

---

전체 코드

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        String input1 = br.readLine();
        String input2 = br.readLine();

        int length1 = input1.length();
        int length2 = input2.length();

        int[][] dp = new int[length1+1][length2+1];

        for (int i=1; i<=length1; i++) {
            for (int j=1; j<=length2; j++) {
                if (input1.charAt(i-1) == input2.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]);
            }
        }

        sb.append(dp[length1][length2]).append("\n");

        Stack<Character> stack = new Stack<>();

        while (length1 > 0 && length2 > 0) {
            if (dp[length1][length2] == dp[length1-1][length2]) {
                length1--;
            }
            else if (dp[length1][length2] == dp[length1][length2-1]) {
                length2--;
            }
            else {
                stack.push(input1.charAt(length1-1));
                length1--;
                length2--;
            }
        }

        while(!stack.isEmpty()) {
            sb.append(stack.pop());
        }

        System.out.println(sb);
    }
}

    

결과