[BOJ/JAVA] 1958번: LCS 3

1958번: LCS 3

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

키워드

LCS(Longest Common Subsequence)

문자열 3개의 LCS를 구하는 프로그램

---

구현

LCS가 무엇인가?

[BOJ/JAVA] 5582번: 공통 부분 문자열

5582번: 공통 부분 문자열 5582번: 공통 부분 문자열 두 문자열이 주어졌을 때, 두 문자열에 모두 포함된 가장 긴 공통 부분 문자열을 찾는 프로그램을 작성하시오. 어떤 문자열 s의 부분 문자열 t란, s에 t가 연속으로 나타나는 것을 말한다. 예를 들 www.acmicpc.net 키워드 두 문자열이 주어졌을 때, 두 문자열에 모두 포함된 가장 긴 공통 부분 문자열을 찾는 프로그램을 작성하시오. 구현 대표적인 LCS문제. 두 문자열 중 공통 부분 문자열을 찾는 것이다. DP를 통해 효율적으로 찾자 cache[][] 배열을 생성하여 [i][j]는 첫 문자열이 i에서 시작하고, 두번에 문자열이 j에서 시작하는 공통 부분 문자열의 길이를 저장한다. 현재 i의 문자와 j의 문자가 같으면 i, j 각각 + ..

https://qpdh.tistory.com/99

가장 긴 공통 부분 수열이다.

예를들어 아래 두 문자열이 있다고 해보자

• abcabcabc

• bcbcbcd

위 문자열에서 a만 전부 제거하면 bcbcbc가 나온다.

아래 문자열도 마찬가지로 d를 제거하면 bcbcbc로 서로 공통 부분 수열중 가장 긴 문자열이 나온다.

이를 구하는 알고리즘이다.

3개는 어떻게 해?

Q : 앞에 두 문자열의 LCS를 구하고 나머지 하나와 그 결과값과 LCS를 구하면 되지 않나요?

안된다.

다음 경우를 살펴보자

• abcabcabcd

• bcbcbcd

• ddddddd

위 두 문자열의 LCS는 bcbcbc가 나온다.

하지만 bcbcbc와 맨 아래 문자열과의 공통 부분 수열이 존재하지 않는다.

하지만 정답은 d이다.

이를 구현하기 위해 기존 2차원 배열로 cache를 저장했던 것에서 3차원 배열로 확장하도록 하자.

N=50이므로 $50^3$은 그렇게 큰 수가 아니기 때문에 충분히 구현이 가능하다.

private static int dp(int firstIndex, int secondIndex, int thirdIndex)

firstIndex, secondIndex, thirdIndex에서 시작하는 공통 부분 문자열의 최댓값 찾기

1. 하나라도 문자열 끝에 도달하는 경우
   • 0을 반환한다.

2. 캐시 값이 이미 존재하는 경우
   • 해당 캐시값을 반환한다.

3. A, B, C 모두 일치하는 경우
   • firstIndex, secondIndex, thirdIndex 모두 1씩 증가시켜 dp를 호출한다.

4. A, B, C가 모두 일치하지 않는 경우(전부 다른 경우, 둘만 같은 경우)
   • firstIndex, secondIndex, thirdIndex 각각 하나씩 증가시켜 dp를 호출한다.

---

코드

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

public class java_1958 {
    static String firstString, secondString, thirdString;

    static int cache[][][];

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        firstString = br.readLine();
        secondString = br.readLine();
        thirdString = br.readLine();

        int result = solution();

        System.out.println(result);

        br.close();
    }

    private static int solution() {
        // 캐시 초기화
        cache = new int[firstString.length()][secondString.length()][thirdString.length()];
        for (int i = 0; i < firstString.length(); i++) {
            for (int j = 0; j < secondString.length(); j++) {
                Arrays.fill(cache[i][j], -1);
            }
        }

        // 시작 인덱스 처리
        int result = 0;

        for (int i = 0; i < firstString.length(); i++) {
            for (int j = 0; j < secondString.length(); j++) {
                for (int k = 0; k < thirdString.length(); k++) {
                    result = Math.max(result, dp(i, j, k));
                }
            }
        }

        return result;
    }

    // firstIndex, secondIndex, thirdIndex에서 시작하는 공통 부분 문자열의 최댓값 찾기
    private static int dp(int firstIndex, int secondIndex, int thirdIndex) {
        // 하나라도 문자열의 끝에 도달하면 0 반환
        if (firstIndex == firstString.length() || secondIndex == secondString.length()
                || thirdIndex == thirdString.length()) {
            return 0;
        }

        // 캐시값이 이미 존재하는 경우
        if (cache[firstIndex][secondIndex][thirdIndex] != -1) {
            return cache[firstIndex][secondIndex][thirdIndex];
        }

        // 캐시 초기화
        cache[firstIndex][secondIndex][thirdIndex] = 0;

        char firstChar = firstString.charAt(firstIndex);
        char secondChar = secondString.charAt(secondIndex);
        char thirdChar = thirdString.charAt(thirdIndex);

        // A, B, C가 모두 일치하는 경우
        // 인덱스 1씩 증가하여 처리
        if (firstChar == secondChar && secondChar == thirdChar) {
            cache[firstIndex][secondIndex][thirdIndex] = Math.max(cache[firstIndex][secondIndex][thirdIndex],
                    1 + dp(firstIndex + 1, secondIndex + 1, thirdIndex + 1));
        }

        // A, B, C가 모두 일치하지 않는 경우
        // firstIndex 증가시켜보기
        // secondIndex 증가시켜보기
        // thirdIndex 증가시켜보기
        else {
            cache[firstIndex][secondIndex][thirdIndex] = Math.max(cache[firstIndex][secondIndex][thirdIndex],
                    dp(firstIndex + 1, secondIndex, thirdIndex));
            cache[firstIndex][secondIndex][thirdIndex] = Math.max(cache[firstIndex][secondIndex][thirdIndex],
                    dp(firstIndex, secondIndex, thirdIndex + 1));
            cache[firstIndex][secondIndex][thirdIndex] = Math.max(cache[firstIndex][secondIndex][thirdIndex],
                    dp(firstIndex, secondIndex + 1, thirdIndex));
        }

        return cache[firstIndex][secondIndex][thirdIndex];
    }
}

---

Uploaded by N2T