백준 1958 ( LCS 3)

문제

---

문자열과 놀기를 세상에서 제일 좋아하는 영식이는 오늘도 문자열 2개의 LCS(Longest Common Subsequence)를 구하고 있었다. 어느 날 영식이는 조교들이 문자열 3개의 LCS를 구하는 것을 보았다. 영식이도 도전해 보았지만 실패하고 말았다.

이제 우리가 할 일은 다음과 같다. 영식이를 도와서 문자열 3개의 LCS를 구하는 프로그램을 작성하라.

 

 

 

풀이

---

LCS 의 개념을 미리 앞에서 풀어 봤기 때문에 문제를 이해하는데는 어렵지 않았다.

conpulake.tistory.com/55

백준 9252 (LCS 2)

위 문제에서 기본적인 LCS를 구하는 방식은 설명을 해놨으니 참고를 바란다.

다른점은 2개 단어를 비교한 위 문제와는 다르게 이문제는 3개의 단어를 비교해야한다.

2개일 때, 2차원 배열로 풀었기 때문에

3개일 때, 3차원 배열로 접근했다.

 

방식은 같다 세개단어의 알파벳이 일치할 시에 +1 을 시켜주고 아닐 경우 제일 큰값을 넣어주면 된다.

2차원 배열일 경우 현재의 위치보다 가로, 세로의 한칸 앞의 배열값을 비교해주면 됐지만,

3차원 배열의 경우 현재위치의 배열 주변의 6개 값을 비교해서 제일 큰값을 저장해줘야한다.

 

 LCS = new int[len3 + 1][len2 + 1][len1 + 1];
        
 for(int i = 1 ; i < len3 + 1 ; i++) {
   	for(int j = 1 ; j < len2 + 1 ; j++) {
   		for(int k = 1; k < len1 + 1 ; k++) {
   			if(string3[i-1] == string2[j-1] && string2[j-1] == string1[k-1] ) {
   				LCS[i][j][k] = LCS[i-1][j-1][k-1] + 1;
   			}
  			else {
   				int u = Math.max(LCS[i-1][j][k], Math.max(LCS[i][j-1][k], LCS[i][j][k-1]));
   				int v = Math.max(LCS[i-1][j-1][k], Math.max(LCS[i-1][j][k-1], LCS[i][j-1][k-1]));
   				
   				LCS[i][j][k] = Math.max(u, v);
   			}
   		}
   	}
 }

 

이렇게 값을 총 6개를 비교해서 제일 큰 값을 저장을 해주면 된다.

 

<전체코드>

import java.io.*;
import java.math.*;
import java.security.*;
import java.text.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.function.*;
import java.util.regex.*;
import java.util.stream.*;

import javax.management.Query;

import static java.util.stream.Collectors.joining;
import static java.util.stream.Collectors.toList;

public class Main {

	static StringBuilder sb = new StringBuilder();
	static int[][][] LCS;
	
    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        

        char[] string1 = bufferedReader.readLine().toCharArray();
        char[] string2 = bufferedReader.readLine().toCharArray();
        char[] string3 = bufferedReader.readLine().toCharArray();
        
        int len1 = string1.length;
        int len2 = string2.length;
        int len3 = string3.length;
        
        LCS = new int[len3 + 1][len2 + 1][len1 + 1];
        
        for(int i = 1 ; i < len3 + 1 ; i++) {
        	for(int j = 1 ; j < len2 + 1 ; j++) {
        		for(int k = 1; k < len1 + 1 ; k++) {
        			if(string3[i-1] == string2[j-1] && string2[j-1] == string1[k-1] ) {
        				LCS[i][j][k] = LCS[i-1][j-1][k-1] + 1;
        			}
        			else {
        				int u = Math.max(LCS[i-1][j][k], Math.max(LCS[i][j-1][k], LCS[i][j][k-1]));
        				int v = Math.max(LCS[i-1][j-1][k], Math.max(LCS[i-1][j][k-1], LCS[i][j-1][k-1]));
        				
        				LCS[i][j][k] = Math.max(u, v);
        			}
        		}
        	}
        }
       
        sb.append(LCS[len3][len2][len1]);
        
        System.out.println(sb);
    }
        
}