[백준] 5582번 공통 부분 문자열 - Java

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

5582번: 공통 부분 문자열

문제

두 문자열이 주어졌을 때, 두 문자열에 모두 포함된 가장 긴 공통 부분 문자열을 찾는 프로그램을 작성하시오.

어떤 문자열 s의 부분 문자열 t란, s에 t가 연속으로 나타나는 것을 말한다. 예를 들어, 문자열 ABRACADABRA의 부분 문자열은 ABRA, RAC, D, ACADABRA, ABRACADABRA, 빈 문자열 등이다. 하지만, ABRC, RAA, BA, K는 부분 문자열이 아니다.

두 문자열 ABRACADABRA와 ECADADABRBCRDARA의 공통 부분 문자열은 CA, CADA, ADABR, 빈 문자열 등이 있다. 이 중에서 가장 긴 공통 부분 문자열은 ADABR이며, 길이는 5이다. 또, 두 문자열이 UPWJCIRUCAXIIRGL와 SBQNYBSBZDFNEV인 경우에는 가장 긴 공통 부분 문자열은 빈 문자열이다.

입력

첫째 줄과 둘째 줄에 문자열이 주어진다. 문자열은 대문자로 구성되어 있으며, 길이는 1 이상 4000 이하이다.

출력

첫째 줄에 두 문자열에 모두 포함 된 부분 문자열 중 가장 긴 것의 길이를 출력한다.

---

유명한 Longet Common Substring 문제이다. DP를 통해 풀 수 있다.

자세한 내용은

https://allmymight.tistory.com/46

에서 확인할 수 있다.

import java.util.*;
public class Main {
    static int[][] dp;
    static String str1;
    static String str2;
    static int ans;
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        str1 = sc.next();
        str2 = sc.next();
        dp = new int[str1.length()+1][str2.length()+1];
        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] > ans)
                        ans = dp[i][j];
                }
                else{
                    dp[i][j] = 0;
                }
            }
        }
        System.out.println(ans);
    }
}

---

자바에서 string 나오는 문제를 풀어볼 겸 선택한 문제이다. LCS 알고리즘은 오랜만에 봐도 확실하게 기억이 난다. 작년만 해도 굉장히 어렵게 느껴졌는데 이해를 하고 나니 문제를 보면 DP가 생각이 나고 디테일만 살짝 생각해보니 쉽게 풀렸다. 포스팅을 작성하면서 이전 포스팅을 가져왔는데 LCS는 생각한 대로지만 LIS문제에서 NlogN 시간 복잡도를 가진 문제는 기억이 안 났다! 다시 한번 보고 가야겠다.

자바의 경우 String의 개별 character에 접근을 할때에는 인덱스를 활용하는 것이 아닌 charAt()이라는 메서드를 활용해야 하는 것을 알아갔다!