[BaekJoon] 9251 LCS (Java)

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]의 값 중 더 큰 값을 현재의 값으로 합니다.

1. 주어진 두 문자열을 각각 first_str과 second_str에 넣어줍니다.
2. first_str을 행, second_str을 열로 의미하는 2차원 배열 dp를 만듭니다. 각 위치의 값은 이전까지의 문자들을 모두 포함한 LCS의 길이를 의미합니다.
3. 행의 각 문자들을 돌면서 이전까지의 문자들을 모두 포함한 LCS의 길이를 구합니다.
   1. 열의 각 문자들을 돌면서 LCS의 길이를 구합니다.
      1. 만약 행 또는 열의 index가 0이라면 이는 패딩으로 생각하고 값을 0으로 합니다.
      2. 만약 행의 현재의 문자와 열의 현재의 문자가 같다면 이전까지의 LCS 길이인 dp[i - 1][j - 1]의 값에 1을 더해주고 해당 값을 현재의 dp 값으로 설정합니다.
      3. 그렇지 않다면 바로 이전 과정인 dp[i - 1][j]와 dp[i][j - 1]의 값 중 더 큰 값을 현재의 값으로 가집니다.
         • 현재 LCS의 길이를 구하는 것이기 때문에 더 긴 값을 현재의 값으로 취합니다.
4. 3번의 반복문이 끝난 후에 행의 마지막 위치 및 열의 마지막 위치에 해당하는 dp의 값이 LCS의 값이므로 해당 값을 출력합니다.