백준 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()]);
}
}
반응형
'알고리즘 > 백준' 카테고리의 다른 글
백준 10845 큐 (JAVA 자바 풀이) (0) | 2022.12.22 |
---|---|
백준 9012 괄호 (JAVA 자바 풀이) (0) | 2022.12.21 |
백준 2565 전깃줄 (JAVA 자바 풀이) (0) | 2022.12.14 |
백준 11054 가장 긴 바이토닉 부분 수열 (JAVA 자바 풀이) (0) | 2022.12.14 |
백준 11055 가장 큰 증가 부분 수열 (JAVA 자바 풀이) (0) | 2022.12.13 |