백준 5582 공통 부분 문자열 & 9251 LCS & 9252 LCS 2 Java

5582 공통 부분 문자열

9251 LCS

9252 LCS2

세 문제 전부 유사한 문제이다.

LCS(최장 공통부분 수열) 알고리즘을 사용한 문제이다.

 

다만 공통 부분 문자열 문제와 LCS문제의 차이점은

공통부분 문자열은 문자열이 연속적이여야하고

LCS 문제들은 연속적이지 않아도 된다.

LCS2 문제는 최장 공통부분 수열을 출력까지 하는 문제이다.

 

LCS 알고리즘은 LIS(최장 증가 부분 수열) 알고리즘과 유사하다.

 

먼저 공통부분 문자열 문제는

연속적이어야 하므로 

문자열이 같을 때 LCS[i-1][j-1]에서 +1을 한 값을 저장하면 된다.

문자열이 같은 것이 여러 번 나올 수 있으므로

2중 for문으로 하나씩 찾아봐야 한다.

 

import java.util.Scanner;
 
public class Q5582 {
 
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        char [] a = scan.nextLine().toCharArray();
        char [] b = scan.nextLine().toCharArray();
        int [][] lcs = new int[a.length+1][b.length+1];
        
        int ans = 0;
        for(int i=1; i<=a.length; i++) {
            for(int j=1; j<=b.length; j++) {
                if(a[i-1] == b[j-1]) {
                    lcs[i][j] = lcs[i-1][j-1]+1;
                    ans = Math.max(ans, lcs[i][j]);
                }
            }
        }
        System.out.println(ans);
    }
}

 

LCS 문제는 연속적이지 않은 문자열중에 최장 공통 문자열이므로

위의 코드에서 살짝 변형 된다.

같지 않을 때도 올 수 있는 값들 중 큰 값으로 초기화해줘야 한다.

그래야 다음에 같은 것을 만났을 때 +1을 할 수 있다.

import java.util.Scanner;
 
public class Q9251 {
 
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        char [] a = scan.nextLine().toCharArray();
        char [] b = scan.nextLine().toCharArray();
        
        int [][] lcs = new int[a.length+1][b.length+1];
        
        for(int i=1; i<=a.length; i++) {
            for(int j=1; j<=b.length; j++) {
                if(a[i-1] == b[j-1]) {
                    lcs[i][j] = lcs[i-1][j-1]+1;
                } else {
                    lcs[i][j] = Math.max(lcs[i][j-1], lcs[i-1][j]);
                }
            }
        }
        System.out.println(lcs[a.length][b.length]);
    }
}

 

LCS2 문제는 위의 알고리즘에 경로를 출력하는 것이 추가된 문제이다.

경로에 추가될 때는 

 if(a[i-1] == b[j-1]) {

    lcs[i][j] = lcs[i-1][j-1]+1;

 } 

이 코드를 통해 추가되는 것이다.

그렇기 때문에 LCS배열과 똑같은 크기의 String 배열을 만들어서

이 때 추가되었다고 표시해준다.

else {

    lcs[i][j] = Math.max(lcs[i][j-1], lcs[i-1][j]);

 }

다른 경우들에는 LCS[i][j-1]값이 들어갔는지 LCS[i-1][j] 값이 들어갔는지

표시해줘서  if(a[i-1] == b[j-1]) 일 때의 경우를 찾아갈 수 있도록 한다.

 

import java.util.Scanner;
 
 
public class Q9252 {
 
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        char [] a = scan.nextLine().toCharArray();
        char [] b = scan.nextLine().toCharArray();
        
        int [][] lcs = new int[a.length+1][b.length+1];
        String [][] solution = new String[a.length+1][b.length+1];
        
        for(int i=1; i<=a.length; i++) {
            for(int j=1; j<=b.length; j++) {
                if(a[i-1]==b[j-1]) {
                    lcs[i][j] = lcs[i-1][j-1]+1;
                    solution[i][j] = "dig";
                } else {
                    lcs[i][j] = Math.max(lcs[i-1][j], lcs[i][j-1]);
                    if(lcs[i][j] == lcs[i-1][j]) {
                        solution[i][j] = "top";
                    } else {
                        solution[i][j] = "left";
                    }
                }
            }
        }
        
        int n = a.length;
        int m = b.length;
        StringBuilder sb = new StringBuilder();
        
        while(solution[n][m] != null) {
            if(solution[n][m].equals("dig")) {
                sb.append(a[n-1]);
                n--;
                m--;
            } else if(solution[n][m].equals("top")) {
                n--;
            }  else if(solution[n][m].equals("left")) {
                m--;
            } 
        }
        System.out.println(lcs[a.length][b.length]);
        System.out.println(sb.reverse().toString());
    }
 
}

참조: https://mygumi.tistory.com/126