[BeakJoon] 5582 공통 부분 문자열 (Java)

🔗 문제 링크

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

📝 문제풀이 방법

처음 문제를 풀었을 때는 단순하게 String라이브러리의 substring()과 contains()메서드를 활용하여 가장 긴 문자열부터 하나씩 비교를 하며 풀이를 하였습니다. 그렇게 풀이를 한 결과 주어진 테스트케이스와 질문하기의 추가 케이스들은 모두 통과를 하나 실제 테스트에서는 통과를 하지 못하였습니다...제가 놓친 무언가가 있는 것 같은데 그것이 무엇인지 모르겠네요😥😥

그리하여 Dynamic programming방식으로 처음부터 문제를 다시 풀이하였습니다.
그 결과 아래와 같이 통과를 하는 결과를 얻을 수 있었습니다.

👨🏻‍💻 처음 작성한 코드 (실패)

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));
        String str1 = br.readLine();
        String str2 = br.readLine();

        if (str1.length() < str2.length()) {
            System.out.println(findResult(str1, str2));
        }
        else {
            System.out.println(findResult(str2, str1));
        }
    }

    private static int findResult(String str1, String str2) {
        for (int i = str1.length(); i > 0; i--) {
            int start = 0;
            int end = start + i;
            while (end <= str1.length()) {
                if (str2.contains(str1.substring(start, end))) {
                    return i;
                }
                start += i;
                end += i;
            }
        }
        return 0;
    }
}

👨🏻‍💻 DP로 작성한 코드

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));
        String str1 = br.readLine();
        String str2 = br.readLine();
        int[][] dp = new int[str1.length()+1][str2.length()+1];
        int max = 0;

        for (int i = 1; i <= str1.length(); i++) {
            for (int j = 1; j <= str2.length(); j++) {
                if (str1.charAt(i-1) == str2.charAt(j-1)) {
                    dp[i][j] = dp[i-1][j-1] +1;
                }

                if (dp[i][j] > max) max = dp[i][j];
            }
        }
        System.out.println(max);
    }
}