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

문제 확인하기:

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 이하이다.

출력

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

예제 입력

ABRACADABRA
ECADADABRBCRDARA

예제 출력

5

생각한 접근법

2차원 배열에 두 문자열의 문자 일치 여부를 기록하기.

입력이 ABCD와 CABC일때 2차원 배열

이후 우하향 대각선의 최대 길이를 찾으면 됨.

시간복잡도

문자열을 이중 반복문으로 조회하므로 O(N^2)의 복잡도가 예상됨. 하지만 N이 4000이하이므로 괜찮다.

공간복잡도

N^2개의 Boolean이므로 1Byte * 4000 * 4000 = 약 16MB. 넉넉하다.

막혔던 점

딱히 없었음.

배운 점

공간복잡도에서 boolean의 메모리를 찾다보니 1bit가 아닌 1byte를 차지함을 알게 됨.

1. 논리형 type ' boolean '은 왜 1bit가 아닌 1byte의 크기를 가질까?

작성한 코드

import java.io.*;
import java.util.*;

public class Main {

    // 조건
    static char[] str1, str2;

    // DP
    static int R, C;
    static boolean[][] isSame;

    public static void main (String[] arg0) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        // 문자열 입력
        str1 = br.readLine().toCharArray();
        str2 = br.readLine().toCharArray();

        // 각 문자열을 비교하는 2차원 배열 생성
        R = str1.length;
        C = str2.length;
        isSame = new boolean[R][C];

        // 배열 완성
        for (int i=0; i<R; i++) {
            for (int j=0; j<C; j++) {
                isSame[i][j] = str1[i] == str2[j];
            }
        }

//        debug();

        // 배열을 위에서부터 조회하여, 가장 긴 문자열 길이 기록.
        int maxLen = 0;
        for (int i=0; i<R; i++) {
            for (int j=0; j<C; j++) {
                if (isSame[i][j]) {
                    maxLen = Math.max(maxLen, checkLen(i, j));
//                    System.out.printf("check (%d,%d) -> maxLen=%d\n", i, j, maxLen);
//                    debug();
                }
            }
        }


        // 출력
        bw.write(String.valueOf(maxLen));
        bw.flush();
        br.close();
        bw.close();
    }

    static int checkLen(int r, int c) {
        // (r,c) ~ (r+k, c+k)로 조사
        int ret = 0;
        int i = r;
        int j = c;
        while (i<R && j<C) {
            if (isSame[i][j]) {
                isSame[i][j] = false;
                ret++;
                i++;
                j++;
            }
            else {
                break;
            }
        }

        return ret;
    }

    static void debug() {
        // debug
        for (int i=0; i<R; i++) {
            for (int j=0; j<C; j++) {
                System.out.printf("%d", isSame[i][j]?1:0);
            }
            System.out.println();
        }
    }
}