[Algorithm] 백준 9252번_LCS2(Java)

🔗 9252번 LCS2

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

9252번: LCS 2

 

문제

---

LCS(Longest Common Subsequence, 최장 공통 부분 수열) 문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다.

예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다.

 

입력

---

첫째 줄과 둘째 줄에 두 문자열이 주어진다. 문자열은 알파벳 대문자로만 이루어져 있으며, 최대 1000글자로 이루어져 있다.

 

출력

---

첫째 줄에 입력으로 주어진 두 문자열의 LCS의 길이를, 둘째 줄에 LCS를 출력한다.

LCS가 여러 가지인 경우에는 아무거나 출력하고, LCS의 길이가 0인 경우에는 둘째 줄을 출력하지 않는다.

 

📝 접근 방법 및 풀이

---

LCS 문제 푸는 법을 모르겠다면 다음 포스팅을 참고하자.

https://myeongju00.tistory.com/44

[Algorithm] 백준 9251번_LCS(Java)

 

이번에는 길이 수만 출력하는게 아니라, LCS도 출력해야 한다.

N → 0 , 즉 하향식으로 값을 저장해 줄 것이기 때문에 후입 선출을 해주는 Stack을 사용하여 데이터를 저장한다.

1. dp[i][j] == dp[i - 1][j]
   : i → i - 1 로 이동
2. dp[i][j] == dp[i][j - 1]
   : j → j - 1 로 이동
3. 1, 2번에 해당하지 않으면 해당 부분은 LCS의 문자열이므로 stack에 저장한다.
   1. st.push(str[i-1]);
   2. 대각선 위로 이동

 

💻 코드

---

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

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


         char[] str1 = br.readLine().toCharArray();
         char[] str2 = br.readLine().toCharArray();

         int length_1 = str1.length;
         int length_2 = str2.length;

         dp = new int[length_1 + 1][length_2 + 1];

         for(int i = 1; i <= length_1; i++) {
             for(int j = 1; j <= length_2; j++) {
                 // (i-1)번째 문자 == (j-1)번째 문자
                 if(str1[i - 1] == str2[j - 1]) {
                     dp[i][j] = dp[i - 1][j - 1] + 1;
                 } else {
                     //이전 열(i-1)과 이전 행(j-1)의 값 중 큰 것으로 갱신
                     dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                 }
             }
         }
         ToString(str1, length_1, length_2);
         System.out.println(dp[length_1][length_2]);
         System.out.println(sb);
     }
     static void ToString(char[] str, int i, int j) {
         Stack<Character> st = new Stack<>();
         while (i > 0 && j > 0) {
             if (dp[i][j] == dp[i - 1][j]) {
                 i--;
             } else if (dp[i][j] == dp[i][j - 1]) {
                 j--;
             } else {
                 st.push(str[i-1]);
                 i--;
                 j--;
             }
         }
         while (!st.isEmpty()) {
             sb.append(st.pop());
         }
     }
 }