[JAVA] 가장 긴 부분 문자열.. (백준17218)

DP 를 풀어야 할 때가 되었다.. 

오늘의 문제는

비밀번호 만들기 https://www.acmicpc.net/problem/17218

문제

최근 들어 개인정보 유출에 대한 뉴스를 많이 본 수형이는 한 사이트의 비밀번호가 유출 되더라도 다른 사이트에서 똑같은 비밀번호로 접속할 수 없도록 사이트마다 비밀번호를 다르게 설정하기로 다짐했다. 많이 고민한 결과 수형이는 눈을 감고 키보드를 막 쳐서 나온 두 문자열에서 공통으로 존재하는 가장 긴 부분 문자열을 비밀번호로 하기로 하였다. 수형이가 눈을 감고 만든 두 문자열이 주어졌을 때 비밀번호를 만드는 프로그램을 만들어보자.

입력

첫째 줄과 둘째 줄에 수형이가 눈을 감고 만든 두 문자열이 주어진다. 문자열은 알파벳 대문자로만 이루어져 있으며, 길이는 최대 40자이다. 빈 문자열은 주어지지 않는다. 가장 긴 부분 문자열은 반드시 하나만 존재한다.

출력

첫 번째 줄에 입력으로 주어진 두 문자열로 만든 비밀번호를 출력한다.

 

입력

AUTABBEHNSA
BCUAMEFKAJNA

 

 

출력

UAENA

AUTABBEHNSA
BCUAMEFKAJNA

 

입력

SETAPPLE 
EATMANY

 

출력

ETA

SETAPPLE 
EATMANY

---

 

풀이

 

최장 공통 부분 문자열(LCS)

은 DP의 대표적인 문제이다.

 

1. Longest Common Subsequence (최장 공통 부분 수열)

• 두 문자열에서 문자들의 순서는 유지하되, 연속적일 필요는 없는 가장 긴 공통 부분을 찾음
• 예: "ACBDE"와 "ABCDE"의 LCS는 "ABDE"
• 중간에 다른 문자가 끼어있어도 됨

2. Longest Common Substring (최장 공통 부분 문자열)

• 두 문자열에서 연속된 문자들로 이루어진 가장 긴 공통 부분을 찾음
• 예: "ABCDE"와 "BCDEF"의 LCS는 "BCDE"
• 반드시 연속된 문자열이어야 함

이 중 1번처럼 연속적이진 않지만 순서를 유지해야하며 공통되는 문자열을 찾아야하는 문제이다.

근데 LCS는 보통 2번의 줄임말이라고 보면 됨

아무튼 dp로 문제를 해결할 수 있는데,

 

1. n*m의 dp배열을 만들고

 

2. 위 그림처럼 일치하는 문자가 나오면 수를 증가시켜주는데, 

최대값을 찾는 것이기 때문에 일치하지 않으면 이전 값 중 큰 값을 저장한다.

 

deepToString으로 dp배열을 찍어보면 그림과 같이 값이 들어간 것을 확인할 수 있다.

 

3. 답을 출력하기 위해 맨 마지막부터 일치하는 문자가 있으면 StringBuilder의 앞에 문자를 추가해 새로운 문자를 만들었다.

참고로 StringBuilder 타입을 문자열로 바꾸어 주어야 함.

그치만 System.out.println()에서는 자동으로 toString()이 호출되고, 다른 상황에서는 명시적으로 result.toString(); 이렇게 써주어야 한다.

그리고 두 문자의 인덱스를 줄여주고,

문자가 다른 경우, dp 배열을 보고 어느 쪽으로 이동할지 결정한다.

-> 위쪽 값이 더 크거나 같으면 위로 이동

-> 왼쪽 값이 더 크면 왼쪽으로 이동한다.

 

최종코드

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String str1 = sc.next();
        String str2 = sc.next();
        int n = str1.length();
        int m = str2.length();

        int[][] dp = new int[n + 1][m + 1];

        // dp 배열 채우기
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (str1.charAt(i - 1) == str2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }

        // 역추적하여 문자 찾기
        StringBuilder result = new StringBuilder();
        while (n > 0 && m > 0) {
            if (str1.charAt(n - 1) == str2.charAt(m - 1)) {
                result.insert(0, str1.charAt(n - 1));
                n--;
                m--;
            } else if (dp[n - 1][m] >= dp[n][m - 1]) {
                n--;
            } else {
                m--;
            }
        }

        System.out.println(result);
    }
}