[백준] code.plus(다이나믹 프로그래밍,JAVA)5582번, 공통 부분 문자열

문제 링크

5582번: 공통 부분 문자열

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

동적 계획법

모든 연산을 수행하면 똑같은 연산을 중복되게 수행하게 되는데 다이나믹 프로그램은 연산한 내용을 따로 저장하여 효율적으로 작성한 프로그램입니다.

 

이 문제에 핵심은

 

1. 2개의 문자열이 주어지고 가장 긴 공통 부분 문자열의 길이를 결과로 출력합니다.

2. 부분 문자열은 문제에서 자세히 설명하고 있습니다.

 

알고리즘 진행 순서.

 

1. 입력되는 문자열을 저장합니다.

 

2. 두 문자열의 각 문자를 비교하여 연속되는 지를 탐색하여 길이를 DP[][]에 저장합니다.

 

3. DP[][]의 최대값을 결과로 출력합니다.

 

 

DP[i][j]의 형태

 

i : 첫 번째 문자열에 현재 문자의 위치

j : 두 번째 문자열에 현재 문자의 위치

 

i번째 문자와 j번째 문자를 포함하는 공통 부분 문자열의 길이를 DP[i][j]에 저장합니다.

 

 

두 문자열의 각 문자를 비교할 때

 

문자가 같을 때

두 문자 다음이 같을 수 있기 때문에 DP[i+1][j+1] = DP[i][j] + 1을 해줍니다.

 

문자가 다를 때

두 문자가 다르기 때문에 다른 문자를 비교합니다.

 

 

Ex.

 

Str1 : ABC

Str2 : BBC

 

DP[0][0] = 0 (A != B)

DP[0][1] = 0 (A != B)

DP[0][2] = 0 (A != B)

 

DP[1][0] = 0 (B == B) : DP[2][1] = DP[1][0] + 1 = 1

DP[1][1] = 0 (B == B) : DP[2][2] = DP[1][1] + 1 = 1

DP[1][2] = 0 (B != C)

 

DP[2][0] = 0 (C != B)

DP[2][1] = 0 (C != B)

DP[2][2] = 1 (C == C) : DP[3][3] = DP[2][2] + 1 = 2

 

최대 공통 부분 문자열의 길이 : 2(BC)

 

 

예제입력 1.

 

1. 입력되는 문자열을 저장합니다.

 

Str1 : ABRACADABRA

Str2 : ECADADABRBCRDARA

 

2. 두 문자열의 각 문자를 비교하여 연속되는 지를 탐색하여 길이를 DP[][]에 저장합니다.

※문자가 같을 때만 DP를 저장하는 것을 표현하였습니다.

 

DP[0][2] = 0 (A == A) : DP[1][3] = DP[0][2] + 1 = 1

DP[0][4] = 0 (A == A) : DP[1][5] = DP[0][4] + 1 = 1

DP[0][6] = 0 (A == A) : DP[1][7] = DP[0][6] + 1 = 1

DP[0][13] = 0 (A == A) : DP[1][14] = DP[0][13] + 1 = 1

DP[0][15] = 0 (A == A) : DP[1][16] = DP[0][15] + 1 = 1

 

DP[1][7] = 1 (B == B) : DP[2][8] = DP[1][9] + 1 = 2

DP[1][9] = 0 (B == B) : DP[2][10] = DP[1][9] + 1 = 1

 

DP[2][8] = 2 (R == R) : DP[3][9] = DP[2][8] + 1 = 3

DP[2][11] = 0 (R == R) : DP[3][12] = DP[2][11] + 1 = 1

DP[2][14] = 0 (R == R) : DP[3][15] = DP[2][14] + 1 = 1

 

...

 

DP[9][8] = 4 (R == R) : DP[10][9] = DP[9][8] + 1 = 5

DP[9][11] = 0 (R == R) : DP[10][12] = DP[9][11] + 1 = 1

DP[9][14] = 0 (R == R) : DP[10][15] = DP[9][14] + 1 = 1

 

DP[10][2] = 0 (A == A) : DP[11][3] = DP[10][2] + 1 = 1

DP[10][4] = 0 (A == A) : DP[11][5] = DP[10][4] + 1 = 1

DP[10][6] = 0 (A == A) : DP[11][7] = DP[10][6] + 1 = 1

DP[10][13] = 0 (A == A) : DP[11][14] = DP[10][13] + 1 = 1

DP[10][15] = 1 (A == A) : DP[11][16] = DP[10][15] + 1 = 2

 

 

3. DP[][]의 최대값을 결과로 출력합니다.

 

 

최대값 DP[9][8] = 5

 

DP[9][8]의 값을 결과로 출력합니다.

 

• BufferedReader를 사용하여 입력 값을 받았습니다.
• 2중 for문을 통해서 문자열의 각 문자열을 비교하여 DP[][]의 값을 저장하였습니다.
• DP[][]의 최대값을 BufferedWriter에 저장합니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

 

import java.io.*;
public class Main {
    static char[] txt1, txt2;	//입력 문자열 저장
    static int[][] DP;		//메모이제이션 배열
    public static void main(String[] args) throws IOException {
        //입력값 처리하는 BufferedReader
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //결과값 출력하는 BufferedWriter
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        txt1 = br.readLine().toCharArray();
        txt2 = br.readLine().toCharArray();
        DP = new int[txt1.length+2][txt2.length+2];
        int answer = 0;
        //DP[][]를 계산 후 최대값 구하기
        for(int i=0;i<txt1.length;i++){
            for(int j=0;j< txt2.length;j++){
                if(txt1[i] == txt2[j]){
                    DP[i+1][j+1] = DP[i][j] + 1;
                    answer = Math.max(answer, DP[i+1][j+1]);
                }
            }
        }
        bw.write(answer + "");	//최대값 BufferedWriter 저장
        bw.flush();		//결과 출력
        bw.close();
        br.close();
    }
}