백준, LCS2(9252, java)

토끼띠NJW 2023. 7. 29. 15:16

문제 설명

두 수열이 주어졌을 때, LCS의 길이와 LCS를 구하는 문제이다.

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

9252번: LCS 2

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

www.acmicpc.net

문제 풀이

첫 번째 접근

https://jiwonna52.tistory.com/71

LCS(Longest Common Subsequence, 최장 공통 부분 수열) java

LCS란? 부분 수열 LCS는 최장 공통 부분 수열로 두 개의 수열이 주어졌을 때, 공통 수열 중 제일 긴 것을 의미한다. 예를 들어서 abcf와 aebwcd가 있다고 생각해 보자. 그렇다면 여기서 나오는 LCS는 abc

jiwonna52.tistory.com

LCS에 관해 정리해둔 글에 문제 풀이가 나와 있다. 사실, 해당 문제도 특별히 응용하는 것보다 알고리즘 자체만 알면 풀 수 있다.

코드

java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

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

        int length1 = str1.length();
        int length2 = str2.length();

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

        for(int i=0; i<length1; i++){
            dp[i][0] = 0;
        }

        for(int i=0; i<length2; i++){
            dp[0][i] = 0;
        }

        for(int i=1; i<length1+1; i++){
            for(int j=1; j<length2+1; j++){
                //만일 두 문자가 같으면
                if(str1.charAt(i-1) == str2.charAt(j-1)){
                    dp[i][j] = 1 + dp[i-1][j-1];
                }else{
                    dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
                }
            }
        }
        /*
        for(int i=0; i<length1; i++){
            for(int j=0; j<length2; j++){
                System.out.print(dp[i][j]);
            }
            System.out.println();
        }*/

        //맨 뒤에서부터 문자를 확인
        int index1 = length1;
        int index2 = length2;
        while(true){

            if(index1 <= 0 || index2 <= 0){
                break;
            }

            if(dp[index1][index2] == dp[index1-1][index2]){
                index1--;
            }else if(dp[index1][index2] == dp[index1][index2-1]){
                index2--;
            }else{
                sb.append(str1.charAt(index1-1));
                index1--;
                index2--;
            }
        }

        String answer = sb.reverse().toString();
        System.out.println(answer.length());
        if(answer.length() != 0){
            System.out.println(answer);
        }
    }
}