백준 9252 LCS 2 java
문제 소개 www.acmicpc.net/problem/9252
내용
LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다.
예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다.
입력
첫째 줄과 둘째 줄에 두 문자열이 주어진다. 문자열은 알파벳 대문자로만 이루어져 있으며, 최대 1000글자로 이루어져 있다.
출력
첫째 줄에 입력으로 주어진 두 문자열의 LCS의 길이를, 둘째 줄에 LCS를 출력한다.
LCS가 여러 가지인 경우에는 아무거나 출력하고, LCS의 길이가 0인 경우에는 둘째 줄을 출력하지 않는다.
해결 방법
아이디어
이 방법을 해결하는 아이디어는 LCS 1 문제에서 했던 것처럼 int배열로 DP가 아닌 String 배열로 DP로 만드는 것이다.
-------
LCS 1의 내용
DP를 이용하여 LCS를 구한다. int형 dp[first.length() + 1][second.length() + 1] 를 생성한다.
각 dp 배열의 값에는 여태까지의 LCS의 개수값이 들어간다.
이후에 이중 반복문으로 first와 second의 각 자리수가 같은지 확인하면서
first.chatAt(i)와 second.charAt(j)가 같으면 dp[i -1][j - 1] 까지의 값에서 + 1한 값을 넣어주고
다르면 dp[i-1][j]와 dp[i][j - 1]값 중 큰값을 넣어주는 방식으로 해결할 수 있다.
--------
LCS 2는 LCS의 문자열 수와 문자열을 출력하는 것으로 String 배열 DP를 만들어서 문자열의 수는 해당 배열의 값의 legnth()를 통해서 얻을 수 있다.
실제 풀이 코드
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String first = br.readLine();
String second = br.readLine();
String[][] stringDP = new String[first.length() + 1][second.length() + 1];
Arrays.fill(stringDP[0], "");
for (int i = 1; i < first.length() + 1; i++) {
Arrays.fill(stringDP[i], "");
for (int j = 1; j < second.length() + 1; j++) {
if (first.charAt(i - 1) == second.charAt(j - 1)) {
stringDP[i][j] = stringDP[i - 1][j - 1] + first.charAt(i - 1);
} else {
if (stringDP[i - 1][j].length() > stringDP[i][j - 1].length()) {
stringDP[i][j] = stringDP[i - 1][j];
} else {
stringDP[i][j] = stringDP[i][j - 1];
}
}
}
}
System.out.println(stringDP[first.length()][second.length()].length());
System.out.println(stringDP[first.length()][second.length()]);
}
}
결과
'알고리즘 문제 > 백준' 카테고리의 다른 글
백준 10775 공항 java (0) | 2021.02.01 |
---|---|
백준 9466 텀 프로젝트 java (0) | 2021.01.27 |
백준 7453 합이 0인 네자리 수 java (0) | 2021.01.23 |
백준 4386 별자리 만들기 java (0) | 2021.01.22 |
백준 2887 행성 터널 java (0) | 2021.01.21 |