[Java] 5582 공통 부분 문자열 - DP

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

5582번: 공통 부분 문자열

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
 
public class Main {
    static String First;
    static String Second;
    static int[][] len;
    static int result;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        First = br.readLine();
        Second = br.readLine();
        int flen = First.length();
        int slen = Second.length();
        len = new int[flen+1][slen+1];
        result =0;
        for(int i=1;i<=flen;i++){
            for(int j=1;j<=slen;j++){
                if (IsSame(First.charAt(i-1), Second.charAt(j-1))){
                    len[i][j] = len[i-1][j-1]+1;
                    if (result<=len[i][j]) result = len[i][j];
                }
            }
        }
        System.out.println(result);
    }
    static boolean IsSame(char A, char B){
        if (A ==B){
            return true;
        }
        return false;
    }
}

두 문자열에 포함된 가장 긴 문자열을 찾는 문제이다.

 

문자열이 어느 인덱스부터 시작할 줄 모르기 때문에, 시작 문자열의 좌표를 인덱스로, 공통 문자열의 길이를 값으로 나타내기 위해

첫 번째 문자열의 길이와 두 번째 문자열의 길이를 담는 배열을 하나 만들었다.

 

문자열 인덱스를 돌면서 만약 같은 문자열이 발견되었다면, (이 부분은 IsSame이라는 메소드를 따로 만들어서 처리 해 주었음)

문자열의 길이를 늘리면서, 만약 가장 긴 문자열의 길이를 저장하는 변수인 result보다 크면 덮어 쓰는 식으로 처리해주었다.

 

음.. 가장 긴 문자열은 한번에 문자열 자체를 찾는게 아니라 그 전 문자열에 하나씩 추가해주는 방식으로 동작하므로 DP를 사용했다고 할 수 있겠다.

 

[시간 초과 코드]

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
 
public class bj5582 {
    static String First;
    static String Second;
    static char first;
    static char second;
    static int cnt;
    static int result;
    static int pre_i;
    static int pre_j;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        First = br.readLine();
        Second = br.readLine();
        int flen = First.length();
        int slen = Second.length();
        result=0;
        for(int i=0;i<flen;i++){
            for(int j=0;j<slen;j++){
                first = First.charAt(i);
                second = Second.charAt(j);
                pre_i = i;
                pre_j = j;
                if (first == second){
                    cnt =1;
                    while(true){
                        if (pre_i+1 >= flen || pre_j+1 >=slen) break;
                        char F = First.charAt(pre_i+1);
                        char S = Second.charAt(pre_j+1);
                        if(!IsSame(F, S)) break;
                        else {
                            cnt += 1;
                            pre_i += 1;
                            pre_j += 1;
                        }
                        if (pre_i >= flen || pre_j >= slen) break;
                    }
                    if(result < cnt) result = cnt;
                }
            }
        }
        System.out.println(result);
    }
    static boolean IsSame(char A, char B){
        if (A ==B){
            return true;
        }
        return false;
    }
}

시간 초과로 FALSE 처리된 코드이다.

특히 문자열을 비교해야하는 경우 많이 날 수 있는 오류같다.

문자열을 비교하며 같은 문자열이 있을 때, index를 기준으로 같은 크기만큼 증가한 인덱스의 값이 다를 때 까지 카운트를

세는 방식으로 동작했다.

문자열의 길이는 각 최대 4000으로, 반복문이 3번 중첩되는 코드로 64000000000.. 640억의 반복이 일어날 수 있다.

시간 초과가 안되는게 이상한 코드라는 것을 알고는 있었는데 혹시하고 해봤다 ㅎㅎㅎㅎ

 

끝!