[BOJ] 9252 LCS 2 - JAVA

1. 문제

9252번: LCS 2

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

첫째 줄에 입력으로 주어진 두 문자열의 LCS의 길이를, 둘째 줄에 LCS를 출력한다.
LCS가 여러 가지인 경우에는 아무거나 출력하고, LCS의 길이가 0인 경우에는 둘째 줄을 출력하지 않는다.

---

2. 풀이

[LCS문제] 에서 사용한 방식으로 최대 길이를 구했다면 dp는 이런식으로 완성된다.

 

가장 끝에서부터 비교해서 올라가면 최장 공통 부분 수열을 구할 수 있다.

1.  lcs[i][j] 값과 위, 오른쪽을 비교해서 같은 값이 있다면 그 값으로 이동한다. 

2.  같은 값이 없다면 대각선(lcs[i-1][j-1])에서 생성된 것이다. 따라서 이전값([i-1][j-1])으로 이동한다. 이동하기 전에 현재 문자열을 StringBuilder에 추가한다.

3.  전부 추가했다면 그 문자열을 뒤집은 것이 최장 공통 부분 수열이다. StringBuilder의 reverse메서드를 사용하면 쉽게 뒤집을 수 있다.

import java.io.*;

public class BOJ_9252_LCS2 {
   public static void main(String[] args) throws IOException {
      BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
      char[] str1 = in.readLine().toCharArray();
      char[] str2 = in.readLine().toCharArray();

      //dp구하기
      int[][] lcs = new int[str1.length+1][str2.length+1];
      for(int i=1;i<=str1.length;i++){
         for(int j=1;j<=str2.length;j++){
            if(str1[i-1]==str2[j-1]) lcs[i][j] = lcs[i-1][j-1]+1;
            else lcs[i][j] = Math.max(lcs[i-1][j], lcs[i][j-1]);
         }
      }

      //최장부분수열구하기
      int y = str1.length, x = str2.length;
      StringBuilder sb = new StringBuilder();
      while(y > 0 && x > 0){
         if(lcs[y][x] == lcs[y-1][x]) y = y-1;
         else if(lcs[y][x] == lcs[y][x-1]) x = x-1;
         else {
            sb.append(str1[y-1]);
            y = y-1;
            x = x-1;
         }
      }

      //길이출력 후 최장부분수열출력
      System.out.println(lcs[str1.length][str2.length]);
      System.out.print(sb.reverse());
   }
}

---

3. 결과