[알고리즘] Java / 백준 / LCS 2 / 9252
[알고리즘] Java / 백준 / LCS 2 / 9252
문제
접근 방식
LCS dp 테이블의 점화식은 다음과 같다.
// 만약 문자열1의 i번째 문자와 문자열2의 j번째 문자가 같으면
// 문자열1의 i-1 번째까지와 문자열2의 j-1번째까지의 공통 부분수열 개수에 1을 더한다.
dp[i][j] = dp[i-1][j-1]+1
// 문자열1의 i번째 문자와 문자열2의 j번째 문자가 다르다면
// 문자열1 i-1번째까지와 문자열2의 j번째까지의 공통 부분수열과
// 문자열1의 i번째까지와 문자열2의 j-1번째까지의 공통 부분수열 개수중 큰 값을 저장한다.
dp[i][j] = Math.min(dp[i-1][j],dp[i][j-1]);
LCS dp 테이블을 만들었다면 맨 오른쪽 아래 값이 LCS의 길이가 된다.
또한 공통 부분수열을 구하는 방법은 다음과 같다.
- LCS배열의 가장 오른쪽 아래에서 시작한다. 결과값을 저장할 문자열 answer를 준비한다.
- dp[i-1][j] 와 dp[i][j-1]중 현재 값과 같은 값을 찾는다
- 만약 같은 값이 있다면 해당 값으로 이동한다.
- 만약 같은 값이 없다면 answer에 현재 위치의 문자를 넣고 dp[i-1][j-1]로 이동한다.
- 2번 과정을 반복하다 0으로 이동하면 종료한다. answer를 역순으로 하면 LCS이다.
코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main_9252 {
public static void main(String[] args) throws IOException{
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=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-1][j], dp[i][j-1]);
}
}
}
int r = str1.length();
int c = str2.length();
int len = dp[r][c];
System.out.println(len);
StringBuilder sb = new StringBuilder();
while(true) {
if(dp[r][c] == dp[r-1][c]) {
r--;
}
else if(dp[r][c] == dp[r][c-1]) {
c--;
}
else {
sb.append(str1.charAt(r-1));
r--;
c--;
}
if(r <= 0 || c <= 0 || dp[r][c] == 0) break;
}
System.out.println(sb.reverse().toString());
}
}
Author And Source
이 문제에 관하여([알고리즘] Java / 백준 / LCS 2 / 9252), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@gandi0330/알고리즘-Java-백준-LCS-2-9252저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)