[백준] 9251 LCS 최장 공통 부분수열 자바 풀이 DP

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

 

 

왜 그때 당시에는 생각이 나지 않았을까. 싶은

DP의 기본중의 기본 문제.

안해보면 낯설지만, 한번 만나면 익숙한 녀석.

 

시작해보자.

 

 

스펙은 이렇다.

 

 

 

 

 

 

 

문제

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

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

입력

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

출력

첫째 줄에 입력으로 주어진 두 문자열의 LCS의 길이를 출력한다.

예제 입력 1 복사

ACAYKP
CAPCAK

예제 출력 1 복사

4

출처

• 문제를 만든 사람: baekjoon
• 데이터를 추가한 사람: bang627, beginnertomaster, eric00513, fs_edge, qpwoeiruty

알고리즘 분류

• 다이나믹 프로그래밍
• 문자열

시간 제한

• Java 8: 0.4 초
• Python 3: 2 초
• PyPy3: 2 초
• Java 8 (OpenJDK): 0.4 초
• Java 11: 0.4 초
• Kotlin (JVM): 0.4 초
• Java 15: 0.4 초

 

 

 

 

 

핵심 설명

 

• 문자 같을 때: 현재 문자를 포함한 최장 공통 부분 수열을 구성할 수 있으므로, dp[i][j] = dp[i-1][j-1] + 1.
• 문자 다를 때: 현재 문자를 포함하지 않는 두 경우의 LCS를 비교하여 더 긴 것을 선택하므로, dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]).

뭐 쉽게말하면, 문자열의 각각의 길이 n과m에 대해

n x m 번 반복문 돌면서 1:1로 문자 비교해보고

같으면 

 

직접 그린 그림

(테스트케이스에서 끝에 R 추가해봤음)

문자 같을 때 = 빨강색 (좌상단에서 +1)

문자 다를 때 + 큰수 = 파랑 실선 (그대로 전달)

문자 다를 때 + 작은수(무시해도되는) = 파랑 점선

 

 

 

집에있던 Elasticsearch 공책 다시보니 디자인 예쁜거같다. 앞으로 알고리즘 단련시 자주 쓸 예정.

 

 

 

 

전체 코드

(문자열까지 구하는 코드 직접 짜봤으니 참고해보세요)

import java.io.*;
import java.util.*;

public class Main{
    public static void main(String[] args) throws IOException{
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        int dap = 0;
        
        // StringTokenizer st = new StringTokenizer(bf.readLine());
        // String s = bf.readLine();
        // Integer n = Integer.parseInt(bf.readLine());
        // Integer n = Integer.parseInt(st.nextToken());
        // Integer k = Integer.parseInt(st.nextToken());
        String a = bf.readLine();
        String b = bf.readLine();
        
        int dp[][] = 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.charAt(i-1) == b.charAt(j-1)){
                    dp[i][j] = dp[i-1][j-1] + 1;
                }
                else{
                    dp[i][j] = Math.max(dp[i][j-1], dp[i-1][j]);
                }
            }
            
            // Arrays.sort(arr[i], Collections.reverseOrder());
            // Arrays.sort(sortedArr);
            // int afterIndex = Arrays.asList(sortedArr).indexOf(arr[i][j]);
            // dap += Math.abs(afterIndex-j);
            // Arrays.sort(arr, (a,b) -> a[1] == b[1] ? (a[2]==b[2] ? a[3]-b[3] : a[2]-b[2]) : a[1]-b[1]);
        }
        dap = dp[a.length()][b.length()];
        
        String dap2 = findStr(a, b, dp);
                    
        // bw.write(String.valueOf(arr[1][0]));
        bw.write(String.valueOf( dap ));
        bw.newLine();
        // bw.write(String.valueOf( dap2 ));
        bw.flush();
        bw.close();
    }
    
    public static String findStr(String a, String b, int[][] dp){
        
        Stack<Character> stk = new Stack<>();
        
        int i = a.length();
        int j = b.length();
        while(i>0 && j>0){
            if(a.charAt(i-1) == b.charAt(j-1)){
                stk.push(a.charAt(i-1));
                i--;
                j--;
            }else if(dp[i-1][j] > dp[i][j-1]){
                i--;
            }
            else{
                j--;
            }
        }
        
        StringBuilder temp = new StringBuilder();
        while(!stk.isEmpty()){
            temp.append(stk.pop());
        }
        
        return temp.toString();
    }
}

 

 

 

참고하기 좋은 링크 (최장 공통 문자열과 함께, 길이와 더불어 값까지 찾아내는 설명도 포함되어 있어 보기좋습니다. 꼭 정독해보세요 !)

https://velog.io/@emplam27/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EA%B7%B8%EB%A6%BC%EC%9C%BC%EB%A1%9C-%EC%95%8C%EC%95%84%EB%B3%B4%EB%8A%94-LCS-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-Longest-Common-Substring%EC%99%80-Longest-Common-Subsequence

[알고리즘] 그림으로 알아보는 LCS 알고리즘 - Longest Common Substring와 Longest Common Subsequence