[Java] 백준 9251 LCS

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

9251번: LCS

 

문제 조건

- 시간 제한 : java 기준 0.4초 

- 메모리 제한 : 256MB

- 정답 비율 : 40%

 

문제 설명 

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

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

 

접근 방법

다이나믹 프로그래밍을 사용한다. -> HOW?

 

DP[문자열1 길이 + 1][문자열2 길이]

 

항상 점화식을 고민하고 진입하자 마치 스프링 서블릿의 init() 같이 

 

점화식 DP[1][3]은 무엇을 의미할까?

문자열1의 1번 index에 해당하는 문자열을 포함하면서 문자열2의 3번 index를 포함하는 곳까지 가장 긴 수열을 기록 

 

구현을 해보자!

 

시간 초과 코드 

import java.io.*;
public class Main {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String str_1 = br.readLine();
        String str_2 = br.readLine();
        int size_1 = str_1.length();
        int size_2 = str_2.length();
        int [][] DP = new int[size_1+1][size_2];
        for (int i = 1; i <= size_1; i++) {
            char target = str_1.charAt(i-1);
            for (int j = 0; j < size_2; j++) {
                if(target == str_2.charAt(j)){
                    int max = 0;
                    for (int k = j - 1; k >= 0; k--) {
                        max = Math.max(DP[i-1][k], max);
                    }
                    DP[i][j] = max + 1;
                }
            }
            for (int j = 0; j < size_2; j++) {
                if(DP[i][j] == 0){
                    DP[i][j] = DP[i-1][j];
                }
            }
        }
        int max = 0;
        for (int i = 0; i < size_2; i++) {
           max = Math.max(DP[size_1][i], max);
        }
        System.out.println(max);
    }
}

 

어떻게 개선할까?

어디서 시간 초과가 나는 걸까? 

시간 복잡도를 생각해 보자! 

최악의 경우 size_1 = 1000 size_2 = 1000 이다. 3중 for문 이니까 
1000 * 1000 * 1000 = 1억 -> 대략 1초 

 

a * 1000 - > a로만 이루어진 문자열1 길이는 1000

a * 1000 ->  a로만 이루어진 문자열2 길이는 1000

-> 1000 * 1000 * 1000 대략 1초의 시간이 걸린다.

 

잘 생각해보면 3중 for문을 2중 for문과 같은 시간 복잡도를 만드는게 가능하다

문자열1에 해댕하는 문자와 문자열2에 해당하는 문자가 똑같을 때 for문이 돌아가고 있는데
for문 범위가 0 <= 범위 <= j - 1 이다. 

 

for문 범위가 0 <= 범위 <= j - 1는 중복 범위를 계속 탐색하는 꼴이다. 

중복 범위를 제외하기 위해서 idx에 저장하고 idx까지만 탐색하도록 코드를 수정하자

정답 코드 

import java.io.*;
public class Main {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String str_1 = br.readLine();
        String str_2 = br.readLine();
        int size_1 = str_1.length();
        int size_2 = str_2.length();
        int [][] DP = new int[size_1+1][size_2];
        for (int i = 1; i <= size_1; i++) {
            char target = str_1.charAt(i-1);
            int idx = 0;
            int max = 0;
            for (int j = 0; j < size_2; j++) {
                if(target == str_2.charAt(j)){
                    for (int k = j - 1; k >= idx; k--) {
                        max = Math.max(DP[i-1][k], max);
                    }
                    DP[i][j] = max + 1;
                    idx = j;
                }
            }
            for (int j = 0; j < size_2; j++) {
                if(DP[i][j] == 0){
                    DP[i][j] = DP[i-1][j];
                }
            }
        }
        int max = 0;
        for (int i = 0; i < size_2; i++) {
           max = Math.max(DP[size_1][i], max);
        }
        System.out.println(max);
    }
}

 

 

감사합니다!