1. 문제 링크
https://www.acmicpc.net/problem/9251
2. 문제
요약
- 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 LCS(Longest Common Subsequence)라고 합니다.
- 두 문자열이 주어질 때, LCS를 찾는 문제입니다.
- 입력: 첫 번째 줄에 길이가 1000보다 작거나 같은 알파벳 대문자로만 이루어진 문자열이 주어지고 두 번째 줄에도 길이가 1000보다 작거나 같은 알파벳 대문자로만 이루어진 문자열이 주어집니다.
- 출력: 첫 번째 줄에 주어진 두 문자열의 LCS 길이를 출력합니다.
3. 소스코드
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
public class Main {
public int getLCSLength(String first_str, String second_str) {
int[][] dp = new int[first_str.length() + 1][second_str.length() + 1];
for(int i = 0; i < dp.length; i++) {
for(int j = 0; j < dp[i].length; j++) {
if(i == 0 || j == 0) {
continue;
} else if(first_str.charAt(i - 1) == second_str.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]);
}
}
}
return dp[first_str.length()][second_str.length()];
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
String first_str = br.readLine();
String second_str = br.readLine();
br.close();
Main m = new Main();
bw.write(m.getLCSLength(first_str, second_str) + "\n");
bw.flush();
bw.close();
}
}
4. 접근
- 해당 문제는 DP를 이용하여 구할 수 있는 문제입니다.
- 첫 번째 줄에 주어진 문자열을 행, 두 번째 줄에 주어진 문자열을 열로 하고 각 위치의 값은 이전까지의 문자들을 모두 포함한 LCS의 길이를 의미합니다.
- 첫 번째 줄의 첫 번째 문자부터 시작하여 마지막 문자까지 두 번째 줄에 주어진 문자열 첫 번째 문자부터 전체에 대해 LCS 길이를 구하고 이전의 길이를 이용하여 두 문자열의 최종 LCS 길이를 구하는 문제입니다.
- 배열에서 행 또는 열의 index가 0이라면, 값을 0으로 둡니다.
- 만약 첫 번째 줄에 주어진 문자열의 현재의 문자(i번째 문자)와 두 번째 줄에 주어진 문자열의 현재의 문자(j번째 문자)가 같다면 이전까지의 LCS 길이인 [i - 1][j - 1]의 값에 1을 더한 값을 현재의 값으로 합니다.
- 만약 그렇지 않다면 현재의 바로 이전 과정인 [i - 1][j]와 [i][j - 1]의 값 중 더 큰 값을 현재의 값으로 합니다.
- 주어진 두 문자열을 각각 first_str과 second_str에 넣어줍니다.
- first_str을 행, second_str을 열로 의미하는 2차원 배열 dp를 만듭니다. 각 위치의 값은 이전까지의 문자들을 모두 포함한 LCS의 길이를 의미합니다.
- 행의 각 문자들을 돌면서 이전까지의 문자들을 모두 포함한 LCS의 길이를 구합니다.
- 열의 각 문자들을 돌면서 LCS의 길이를 구합니다.
- 만약 행 또는 열의 index가 0이라면 이는 패딩으로 생각하고 값을 0으로 합니다.
- 만약 행의 현재의 문자와 열의 현재의 문자가 같다면 이전까지의 LCS 길이인 dp[i - 1][j - 1]의 값에 1을 더해주고 해당 값을 현재의 dp 값으로 설정합니다.
- 그렇지 않다면 바로 이전 과정인 dp[i - 1][j]와 dp[i][j - 1]의 값 중 더 큰 값을 현재의 값으로 가집니다.
- 현재 LCS의 길이를 구하는 것이기 때문에 더 긴 값을 현재의 값으로 취합니다.
- 3번의 반복문이 끝난 후에 행의 마지막 위치 및 열의 마지막 위치에 해당하는 dp의 값이 LCS의 값이므로 해당 값을 출력합니다.