[백준] 9252: LCS 2 (DP) - JAVA

class 5

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

 

 

 

 

# 문제

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

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

 

 

# 예제

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

ACAYKP
CAPCAK

 

 

출력

4
ACAK

 

# 필요개념

수열의 길이와 해당 수열을 구하는 일을 동시에 진행하려고 하니까 막막해서 나누어 구하기로 했다. 이전에도 LCS 길이를 구하는 문제를 풀었었기 때문에, 이러면 안 되지만 그때의 기억에 의존해서 풀었다.

 

해당 문제에서 문자열 두개를 입력받고, 각각 str1, str2라고 이름을 지었다.

• 만약 str1.charAt(i)와 str2.charAt(j)가 같다면 LCS의 길이가 1만큼 증가한다.
• 같지 않으면 이전의 길이가 그대로 들어온다. 

 

위 조건을 토대로 이차원 배열을 만들어 문제를 풀었고, 점화식을 작성하면 아래와 같다.

if (str1.charAt(i - 1) == str2.charAt(j - 1)) {
	dp[i][j] = dp[i - 1][j - 1] + 1;
}

 

 

이렇게 dp 배열에 길이를 넣어두고, dp 배열을 역추적하여 공통부분수열을 구하였다.

y, x에 인덱스가 들어있다고 할 때

• str1.charAt(y) 와 str2.charAt(x) 가 같으면 스트링빌더에 추가, y와 x를 각각 1씩 줄임
• str1.charAt(y) 와 str2.charAt(x) 가 다르고
  • dp[y - 1][x] > dp[y][x - 1] 이면 -> y를 1만큼 줄임
  • dp[y - 1]]x] < dp[y][x - 1] 이면 -> x를 1만큼 줄임

 

역추적한 결과인 스트링빌더를 reverse()를 이용해 반대로 출력한다.

 

# Code

import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String str1 = br.readLine();
        String str2 = br.readLine();
        int[][] dp = 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.charAt(i - 1) == str2.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]);
                  }
            }
        }
        System.out.println(dp[str1.length()][str2.length()]);

        StringBuilder sb = new StringBuilder();
        int y = str1.length();
        int x = str2.length();

        while (y > 0 && x > 0) {
            if (str1.charAt(y - 1) == str2.charAt(x - 1)) {
                sb.append(str1.charAt(y - 1));
                y--;
                x--;
            } else if (dp[y - 1][x] > dp[y][x - 1]) {
                y--;
            } else x--;
        }

        System.out.println(sb.reverse().toString());
    }
}

 

 

# 결과