[백준] G4 9252번 LCS 2 (JAVA)

문제 출처 - Baekjoon Online Judge

문제는 여기

9252번: LCS 2

[문제] 

LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다.

예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다.

[입력]

첫째 줄과 둘째 줄에 두 문자열이 주어진다. 문자열은 알파벳 대문자로만 이루어져 있으며, 최대 1000글자로 이루어져 있다.

[출력]

첫째 줄에 입력으로 주어진 두 문자열의 LCS의 길이를, 둘째 줄에 LCS를 출력한다.

LCS가 여러 가지인 경우에는 아무거나 출력하고, LCS의 길이가 0인 경우에는 둘째 줄을 출력하지 않는다.

 

---

[풀이]

1. 2개의 문자열을 입력받아준다.

2. dp 배열을 만들어 1번 문자열은 가로, 2번 문자열은 세로로 잡아주고 0으로 초기화해준다.

3. 문자를 비교하면서 같은 문자가 나왔다면 왼쪽 대각선 위의 값 + 1을 dp 배열에 넣어준다.

4. 문자가 다르다면 왼쪽과 위쪽 값을 비교해 더 큰 값을 입력해준다.

5. 4. 의 결과값을 출력해준다.

6. 스택을 만들어 dp 배열을 탐색하며 같은 문자가 올 때 결과를 스택에 담아준다.

7. 같은 문자들이 담긴 스택을 pop하면서 결과를 출력해준다.

[접근]

1. 이전에 풀었던 LCS문제에 결과값만 출력해주는 걸 추가해주면 되는 문제였다.

이전 문제는 아래 글을 참고하자.

2022.07.02 - [문제 풀이/Baekjoon] - [백준] G5 LCS (JAVA)

[백준] G5 LCS (JAVA)

[코드]

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

public class Main {

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		String str1 = br.readLine();
		String str2 = br.readLine();
		
		int[][] dp = new int[str1.length() + 1][str2.length() + 1];
		
		for (int i = 0; i <= str1.length(); i++) {
			dp[i][0] = 0;
		}
		for (int i = 0; i <= str2.length(); i++) {
			dp[0][i] = 0;
		}
		
		// LCS 알고리즘 적용
		for (int i = 1; i <= str1.length(); i++) {
			for (int j = 1; j <= str2.length(); 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][j - 1], dp[i - 1][j]);
			}
		}
		
		// LCS의 결과 출력
		System.out.println(dp[str1.length()][str2.length()]);
		
		// 해당 LCS 문자열의 결과를 담기위한 스택
		Stack<Character> stack = new Stack<>();
		
		int a = str1.length();
		int b = str2.length();
		
		// 스택에 담으므로 역순으로 탐색
		while (a != 0 && b != 0) {
			// 같은 문자라면
			if (str1.charAt(a - 1) == str2.charAt(b - 1)) {
				// 스택에 담아주기
				stack.add(str1.charAt(a - 1));
				a--;
				b--;
			}
			// 다른 문자의 경우
			// 왼쪽과 위쪽의 값 중 큰 것을 가지고 왔기 때문에 가져온 값으로 맞춰주기 위해 해당 값을 빼줌 
			else if (dp[a][b] == dp[a - 1][b]) {
				a--;
			} else if (dp[a][b] == dp[a][b - 1]) {
				b--;
			}
		}
		
		// 역순으로 빼주기
		while (!stack.isEmpty())
			System.out.print(stack.pop());
	}
}