공부하기/백준

[Java] 백준 풀기 9251 - LCS

XEV 2024. 4. 5. 22:54

자바 백준 9251번

골드 5

https://www.acmicpc.net/problem/9251

 

9251번: LCS

LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다.

www.acmicpc.net

 

 

 

 

 

문제 보기

분류: 다이나믹 프로그래밍, 문자열

 

 

 

 

 

코드 풀이

import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
// 두 문자열 입력
String str1 = sc.nextLine();
String str2 = sc.nextLine();
// LCSCalculator 객체 생성
LCSCalculator lcsCalculator = new LCSCalculator();
// LCS 길이 계산
int lcsLength = lcsCalculator.calculateLCSLength(str1, str2);
// 계산된 LCS의 길이 출력
System.out.println(lcsLength);
}
}
class LCSCalculator {
// LCS 길이를 계산하는 메서드
public int calculateLCSLength(String str1, String str2) {
// 각 문자열의 길이 구하기
int m = str1.length();
int n = str2.length();
// DP 테이블 초기화
int[][] dp = new int[m + 1][n + 1];
// 다이나믹 프로그래밍을 통해 LCS 길이 계산
// dp[i][j]는 문자열 str1의 처음부터 i번째 문자까지, 그리고 문자열 str2의 처음부터 j번째 문자까지의 LCS 길이를 나타냄
// 문자열 str1의 각 문자를 순회
for (int i = 1; i <= m; i++) {
// 문자열 str2의 각 문자를 순회
for (int j = 1; j <= n; j++) {
if (str1.charAt(i - 1) == str2.charAt(j - 1))
// 이전까지의 LCS 길이에 현재 문자를 추가하면서 LCS의 길이를 증가
dp[i][j] = dp[i - 1][j - 1] + 1;
else
// 현재 비교하는 문자가 다르다면, 이전까지의 LCS 중 최대값을 선택하여 현재 위치의 LCS 길이를 결정
dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
}
}
// 계산된 LCS의 길이 반환
return dp[m][n];
}
}