[백준] 공통 부분 문자열

문제

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

알고리즘

• DP
• 문자열

풀이

많이 어려웠다. DP와 문자열을 조합해서 풀어야 하기 떄문에..
확실하게 이해해서 다음에 꼭 풀어야겠다.

일단 두 문자열의 공통되고 연속된 부분 문자열을 찾는게 핵심이다.
그러려면 앞에서부터 한 문자씩 비교해야 하는데 for문으로 일일히 돌려서 풀면 당연히 시간초과가 난다.
이럴떄는 DP를 사용해야 하는데 아직은 DP를 사용해야 한다는 감이 잘 오지는 않는다.

만약 두개의 문자열이 같으면 현재 좌표인 x,y의 x+1, y+1을 기존 값에서 +1을 해주어야 한다.
왜냐하면 두 문자열이 같기 때문에 x,y 둘다 +1을 해준 좌표에 +1을 해주어야 한다.
나머지 좌표는 사실 알 필요가 없다. 왜냐하면 공통으로 같으면서 연속된 문자열의 좌표만 알면 되기 때문이다.

그리고 나서 해당 값중에서 가장 큰 값을 Math 함수로 찾아주기만 하면 된다.

풀이를 보면 쉬운데 아무 정보가 없는 상태에서는 어렵다.

요약

1. 두 문자열의 공통된 연속 문자열이기 때문에 DP를 떠올린다.
2. 두 문자가 같은 경우에는 다음 좌표인 x+1, y+1을 x,y 값에 +1을 해준다.
3. 두 문자가 다른 경우는 확인하지 않아도 된다.

참고

https://comgong-man.tistory.com/200

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

class Main {

    public int solution(String s, String t) {

        int answer = 0;
        int[][] dp = new int[s.length() + 1][t.length() + 1];

        for (int i = 0; i < s.length(); i++) {
            for (int j = 0; j < t.length(); j++) {
                if (s.charAt(i) == t.charAt(j)) {
                    dp[i+1][j+1] = dp[i][j] + 1;
                    answer = Math.max(answer, dp[i + 1][j + 1]);
                }
            }
        }

        return answer;
    }

    public static void main(String[] args) throws IOException {

        Main solution = new Main();
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        String s = br.readLine();
        String t = br.readLine();

        System.out.println(solution.solution(s, t));

    }
}