백준 9251 LCS (JAVA 자바 풀이)

백준 9251 LCS (JAVA 자바 풀이)

 

---

 

 

📌 문제 

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

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

 

 

⚔ 입력

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

 

 

📣 출력

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

 

 

 

 

---

 

 

 

💎 문제 분석

 

 

최장 공통 부분 수열 문제이다. LIS의 응용 문제라고 할 수 있다. 

 

2차원 배열을 놓고 카운팅을 해주는 방식으로 풀이하면 된다. 아래 그림과 같은 손코딩을 하고 이것을 어떻게 만들지를 고민해보았다. 

 

 

 

한번 count를 up 시켜주어서 올라온 상태에서 그것을 유지해주어야 한다. (=다시 0이 되면 안 된다)

 

이를 고려할 때 match가 발생하는 경우 뿐만 아니라 발생하지 않는 경우에도 default 값을 설정해주어야 한다.

 

그 방법으로 위에것 혹은 이전 것을 가져오는 로직을 구현한다. 

 

dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);    // 위에 것 혹은 이전 것

 

이 과정에서 i=0인 경우 에러가 발생하기 때문에 i, j를 1부터 카운팅 해주는 방식으로 설정했다. 

 

 

마지막 K값이 일치하면서 counting이 4가 되는 것을 확인할 수 있다.

 

 

💡 코드 구현

 

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

public class Main {

	public static void main(String[] args) throws IOException {

		BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
		String string1 = bufferedReader.readLine();
		String string2 = bufferedReader.readLine();

		int[][] dp = new int[string1.length()+1][string2.length()+1];

		for (int i = 0; i <= string1.length(); i++) {
			for (int j = 0; j <= string2.length(); j++) {
				if (i==0 || j==0) {
					dp[i][j]=0;
					continue;
				}
				if (string1.charAt(i-1) == string2.charAt(j-1)) {
					dp[i][j] = Math.max(dp[i-1][j-1], dp[i-1][j-1] + 1);
					continue;
				}
				dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);	// 위에 것 혹은 이전 것
			}
		}

//		for (int i =0; i<string1.length(); i++){
//			System.out.println(Arrays.toString(dp[i]));
//		}
		System.out.println(dp[string1.length()][string2.length()]);
	}
}