1958번: LCS 4

Skele·2025년 4월 16일

algorithm dynamic programming

알고리즘 문제 풀이

목록 보기

9/21

1958번: LCS 4

알파벳 소문자로 이루어진 문자열 3개가 주어진다.
이 세 문자열의 LCS (최장 공통 부분 수열) 의 길이를 구하라.

조건

각 문자열의 길이 ≤ 100
문자열은 알파벳 소문자로만 구성됨

접근

LCS

LCS를 구하는 다이나믹 프로그래밍 문제이다.
다만, 두 문자열이 아닌 세 문자열에서 구해야한다.

LCS + LCS ( 실패 )

두 문자열을 먼저 비교하고, 나온 LCS를 남은 문자열과 비교할 생각을 하였다.
S1 X S2 + S12 X S3이 시간복잡도 면에서 S1 X S2 X S3보다 나을 거라 생각했기 때문이다.
다만, 후술할 문제점에 의해 이 방법은 실패한다.

3차원 LCS

기존 LCS에서 확장하여 두 문자열이 아닌 세 문자열을 비교하는 방식으로 진행한다.

코드

실패한 코드

두 문자열의 LCS의 크기와 구성하는 문자열을 Subsequence라는 객체에 담아 저장
첫번째와 두번째 문자열의 LCS를 구한다
도출한 LCS와 세번째 문자열로 LCS를 다시 구한다.

순진하게 순차로 구해도 될 것이라 생각했지만, 이 접근 방식에는 큰 오류가 있다.

첫번째와 두번째 문자열로 구한 LCS가 여러개일 수 있다.
이 방식에서는 하나의 LCS와 세번째 문자열만을 연산한다.

따라서 모든 경우의 수를 고려하지 못한 풀이법인 것이다.

import java.util.*;
import java.io.*;

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		
		input(in);
		solve();	
	}
	
	static String first;
	static String second;
	static String third;
	static void input(BufferedReader in) throws IOException {
		first = in.readLine();
		second = in.readLine();
		third = in.readLine();
	}
	
	static void solve(){
		Subsequence[][] dp = new Subsequence[first.length()+1][second.length()+1];
		
		for(int i = 0; i <= first.length(); i++) {
			dp[i][0] = new Subsequence(0, "");
		}
		for(int i = 0; i <= second.length(); i++) {
			dp[0][i] = new Subsequence(0, "");
		}
		
		for(int i = 0; i < first.length(); i++) {
			for(int j = 0; j < second.length(); j++) {
				if(first.charAt(i) == second.charAt(j)) {
					dp[i+1][j+1] = new Subsequence(dp[i][j].length + 1, dp[i][j].sequence + first.charAt(i));
				} else {
					if(dp[i+1][j].length > dp[i][j+1].length) {
						dp[i+1][j+1] = dp[i+1][j];
					} else {
						dp[i+1][j+1] = dp[i][j+1];
					}
				}
			}
		}
		
		String lcs12 = dp[first.length()][second.length()].sequence;
		
		int[][] dp2 = new int[lcs12.length()+1][third.length()+1];
		
		for(int i = 0; i < lcs12.length(); i++) {
			for(int j = 0; j < third.length(); j++) {
				if(lcs12.charAt(i) == third.charAt(j)) {
					dp2[i+1][j+1] = dp2[i][j] + 1;
				} else {
					dp2[i+1][j+1] = Math.max(dp2[i+1][j], dp2[i][j+1]);
				}
			}
		}
		
		System.out.println(dp2[lcs12.length()][third.length()]);
		
	}
	
	static class Subsequence{
		int length;
		String sequence;
		public Subsequence(int l, String s) {
			length = l;
			sequence = s;
		}
	}
}

성공한 코드

세 문자열을 같이 비교하는 방식으로 진행한다.
시간 복잡도가 S1 X S2 X S3 이지만, 각 문자열의 길이가 100이하이므로 안전하다.

static void solve(){
	int[][][] dp = new int[first.length()+1][second.length()+1][third.length()+1];
	
	
	for(int i = 0; i < first.length(); i++) {
		for(int j = 0; j < second.length(); j++) {
			for(int k = 0; k < third.length(); k++) {
				if(first.charAt(i) == second.charAt(j) && second.charAt(j) == third.charAt(k)) {
					dp[i+1][j+1][k+1] = dp[i][j][k]+1;
				} else {
					dp[i+1][j+1][k+1] = Math.max(dp[i][j+1][k+1], Math.max(dp[i+1][j][k+1], dp[i+1][j+1][k]));
				}
			}
		}
	}
	
	System.out.println(dp[first.length()][second.length()][third.length()]);
}