[백준] 단계별로 풀어보기(단계:27, 동적 계획법과 최단거리 역추적,JAVA)9252번, LCS 2

문제 링크

9252번: LCS 2

---

주의사항

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

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

---

문제 설명

---

접근 방법

동적 계획법

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

 

더 자세한 내용은 링크를 남겨두겠습니다.

동적 계획법 - 위키백과, 우리 모두의 백과사전

이 문제에 핵심은

1. 증가하는 수열 중 가장 긴 수열의 길이를 결과로 출력해야 합니다.

 

배열

 

str1 : 입력되는 첫 번째 문자열

 

str2 : 입력되는 두 번째 문자열

 

DP[][] : 메모이제이션 배열

 

DP[i][j]에 저장되는 값은 문자열에서 str2에 1~i 범위에 문자에서 str2에 1~j까지 범위에서 가장 긴 수열의 길이를 저장됩니다.

 

예제입력 1에 DP[][]의 값을 표로 살펴보면

	1(A)	2(C)	3(A)	4(Y)	5(K)	6(P)
1(C)	1	1	1	1	1	1
2(A)	1	1	2	2	2	2
3(P)	1	1	2	2	2	3
4(C)	1	2	2	2	2	3
5(A)	1	2	3	3	3	3
6(K)	1	2	3	3	4	4

 

DP[3][3]을 구할 때에는

str1[1~3] = ACA 

str2[1~3] = CAP

가장 긴 수열은 CA로 길이는 2가 저장됩니다.

 

DP[5][3]을 구할 때에는

str[1~3] = ACA

str[1~5] = CAPCA

가장 긴 수열은 ACA로 길이는 3이 저장됩니다. 

 

표를 통해 규칙을 찾을 수 있습니다.

DP[i][j]을 구할 때

str2[i] == str1[j]이면 DP[i][j] = DP[i-1][j-1] + 1

str2[i] == str2[j]이면 DP[i][j] = Math.max(DP[i-1][j], DP[i][j-1])

 

규칙을 적용해서 표에 대한 값을 살펴보면

DP[2][3]을 구할 때

str2[2]('A') == str1[3]('A')

DP[2][3] = DP[2-1][3-1] + 1 = 1 + 1 = 2

 

DP[5][4]을 구할 때

str2[5]('A') != str1[4]('Y')

DP[5][4] = Math.max(DP[5-1][4], DP[5][4-1]) = Math.max(2, 3) = 3

 

위 과정을 통해 DP[][]값을 구성한 뒤 DP[str2.length][str1.length]의 값이 최대 수열의 길이를 가지게 됩니다.

 

최대 수열의 길이는 DP[6][6]의 값인 4를 결과로 출력합니다.

 

최대 길이의 수열의 문자열도 결과로 출력하기 때문에 저는 Stack을 사용하여 결과를 출력하였습니다.

	1(A)	2(C)	3(A)	4(Y)	5(K)	6(P)
1(C)	1	1	1	1	1	1
2(A)	1	1	2	2	2	2
3(P)	1	1	2	2	2	3
4(C)	1	2	2	2	2	3
5(A)	1	2	3	3	3	3
6(K)	1	2	3	3	4	4

 

DP[][]의 값은 최대 길이를 나타내는 것으로 최대 길이면서 str2[i] == str1[j]인 값들을 Stack에 저장한 뒤에 결과로 출력하였습니다.

 

길이 : 4 = DP[6][5] = 'K'

길이 : 3 = DP[5][3] = 'A'

길이 : 2 = DP[4][2] = 'C'

길이 : 1 = DP[2][1] = 'A'

 

스택은 LIFO(후입선출)로 결과로 출력할 때에는 "ACAK"로 결과로 출력됩니다.

 

문제를 해결한 알고리즘의 과정입니다.

1. 입력되는 문자열 2개를 저장합니다.

2. 규칙을 통해 DP[][]를 구성합니다.

3. DP[str1.length][str2.length]의 값은 수열의 최대 길이로써 결과로 출력하였습니다.

4. 최대 길이 수열의 문자열을 Stack와 DP를 사용하여 문자열을 출력하였습니다.

 

• BufferedReader를 사용하여 입력 값을 받았습니다.
• toCharArray()를 통해 입력되는 문자열을 문자 배열에 저장하였습니다.
• 반복문 및 규칙을 통해 DP[]를 구성하고 최대 길이를 출력하는 cal 함수를 실행하였습니다.
• 최대 길이 수열의 문자열을 구하기 위해 Stack을 사용하는 LCS 함수를 실행하였습니다.
• BufferedWriter에 DP[str2.length][str1.length]의 저장된 수열의 최대 길이를 저장하였습니다.
• BufferedWriter에 Stack에 저장된 문자들을 저장하였습니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

• cal 함수는 반복문과 규칙을 통해 DP구성 및 최대 길이를 반환하였습니다.
• LCS 함수는 문자열 구하는 규칙을 통해 Stack에 저장하여 반환하였습니다.

import java.io.*;
import java.util.*;
public class Main{
	static char[] str1, str2;	//입력되는 문자열 저장하는 문자 배열
	static int[][] DP;		//메모이제이션 배열
    public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //입력값 처리하는 BufferedReader
    	BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        //결과값 출력하는 BufferedWriter
        //---------입력값 저장 및 배열 초기화-----------
    	str1 = br.readLine().toCharArray();
    	str2 = br.readLine().toCharArray();
    	DP = new int[str2.length+1][str1.length+1];
    	int length = cal();		//DP 구성 및 최대 길이 받는 함수 실행
    	Stack<Character> lcsValue = LCS(length);	//최대 길이 수열의 문자열 받는 함수 실행
    	bw.write(length + "\n");		//최대 길이 BufferedWriter 저장
    	while(!lcsValue.isEmpty()) 		//Stack에 저장된 값 BufferedWriter 저장
    		bw.write(lcsValue.pop());
    	bw.flush();		//결과 출력
    	bw.close();
    	br.close();

    }
    //--------규칙과 반복문을 통해 DP를 구성하고 최대 길이를 반환하는 함수--------
    static int cal() {
    	for(int i=1;i<=str2.length;i++) {
    		for(int j=1;j<=str1.length;j++) {
    			if(str2[i-1] == str1[j-1])		//규칙1.
    				DP[i][j] = DP[i-1][j-1] + 1;
    			else		//규칙2.
    				DP[i][j] = Math.max(DP[i][j-1], DP[i-1][j]);
    		}
    	}
    	return DP[str2.length][str1.length];	//최대 길이 반환
    }
    //------최대 길이의 수열의 문자열을 Stack을 통해 구성 및 반환하는 함수-------
    static Stack<Character> LCS(int length) {
    	Stack<Character> stack = new Stack<Character>();
    	for(int i=str2.length;i>0;i--){
    		for(int j=str1.length;j>0;j--) {
            	//Stack 구성
    			if((str2[i-1] == str1[j-1]) && (DP[i][j]==length)) {
    				stack.add(str1[j-1]);
    				length--;
    				break;
    			}		
    		}
    		if(length==0)
    			break;
    	}
    	return stack;		//결과 Stack 반환
    }
}