[BOJ] BOJ 9252번 'LCS 2' (Java) (+ LCS 개념)

[백준 9252번 'LCS 2']

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

 

[접근 방식]

LCS(Longest Common Subsequence), "최장 공통 부분 수열" 은 '대상 문자열들의  문자 사이를 건너뛰어 공통되면서 가장 긴 부분 문자열'을 의미한다.

위 문제의 예제1을 보면,

"ACAYKP" , "CAPCAK" 이렇게 두개의 문자열의 LCS 를 구하고자 한다.

 

"ACAYKP"

"CAPCAK"

 

LCS = "ACAK" 이다.

꼭 연속된 문자가 아니더라도, 순서대로 공통된 문자들의 집합의 가장 긴 사례를 구하는 것이 "최장 공통 부분 수열" 이다.

 

LCS에 대한 자세한 설명은 https://buly.kr/7mAqbah 를 참고.

 

문제 해결 키워드는 "LCS"를 "DP"를 이용하여 구성하는 것이다.

 

dp 배열을 채워가며 두 문자열의 LCS 길이를 구하고,

dp 배열 역추적을 통해 LCS를 구한다. 

 

[Java 코드]

/**
 * BOJ_9252 LCS 2
 * https://www.acmicpc.net/problem/9252
 * keyword - 
 */

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));

    //두 문자열 입력
    String A = br.readLine();
    String B = br.readLine();

    //두 문자열 길이
    int n = A.length();
    int m = B.length();

    //LCS 길이 dp 배열
    int[][] dp = new int[n + 1][m + 1];

    for (int i = 1; i <= n; i++) {
      for (int j = 1; j <= m; j++) {
        if (A.charAt(i - 1) == B.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]);
        }
      }
    }

    //LCS 길이 출력
    System.out.println(dp[n][m]);

    //LCS가 존재하지 않으면 그대로 종료
    if (dp[n][m] == 0) return;


    //dp 배열 역추적하여 LCS 구하기
    StringBuilder lcs = new StringBuilder();
    int i = n, j = m;
    while (i > 0 && j > 0) {
      if (A.charAt(i - 1) == B.charAt(j - 1)) {
        lcs.append(A.charAt(i - 1));
        i--;
        j--;
      } else if (dp[i - 1][j] > dp[i][j - 1]) {
        i--;
      } else {
        j--;
      }
    }

    //LCS 출력
    System.out.println(lcs.reverse().toString());
  }
}

 

[Rewind]

1. 어려웠던 점

- LCS의 개념에 대해 명확히 알지 못했다.

- LCS를 명확히 이해 한 후에도 DP를 이용하여 LCS를 구하는 방법을 스스로 도출하지 못했다.

- 유명한 개념인 "LCS : 최장 공통 부분 수열" , "LIS : 최장 증가 부분 수열" 등의 개념을 명확히 이해하지 못하고 있었고,

구현 방식 또한 이해하고 있지 못했다.

 

2. 알게된 점

- LIS, LCS의 구현 방식과 개념에 대해 다시끔 인지하게 되었다.

 

3. 개선방안

- 절대 잊지 않았으면 좋겠다.