백준 9252 (LCS 2)

문제

---

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

예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다.

 

 

 

 

 

풀이

---

이문제를 분류를 두는것이 어려웠다.

동적 계획법(Danamic Programming)을 기반을 한 String 문제이기 때문이다.

하지만 중요한건 문자열 이므로 문자열 카테고리에 넣는다.

 

LCS는 두가지가있다.

• Longest Common Substring (공통 부분 문자열)
• Longest Common Subsequence (공통 부분 수열)

ACAYKP

CAPCAK

이 두개의 문자열에서 

Substring -> CA 

Subsequence -> ACAK 

이렇게 차이가 생긴다.

 

풀이 방식은 코드를 보면서 설명을 하겠다.

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

 

LCS 라는 이중배열을 두고 가로에는 첫번째 문자열 세로에는 두번째 문자열을 저장한다고 가정한다.

위 의 반복문을 통해 만들어지는 LCS 이중 배열은 아래의 그림과 같이 구성이 된다.

 

실제 배열에서는 알파벳이 저장되지 않지만 편의상 같이 넣어서 이해를 돕도록 했다.

공통 부분수열은 순서가 섞이지 않는 선에서 같은 부분수열이 존재하면 되기 때문에 알파벳이 같다면 +1 을 시켜줍니다.

 

공통 부분 수열의 길이는 LCS[len2][len1]의 크기와 같다.

 

 

공통 부분 수열의 값을 찾는 방식이다.

int i = len2, j = len1;
Stack<Character> stack = new Stack<>();
        
while(i >= 1 && j >= 1) {
  	if(LCS[i][j] == LCS[i-1][j])
   		i--;
   	
   	else if( LCS[i][j] == LCS[i][j-1])
   		j--;
    	
   	else {        		
   		stack.push(string2[i-1]);
   		i--;
   		j--;
   	}
}

 

위 그림은 반복문의 구동 방식을 그림으로 표현한 것이다.

 

3가지 방식으로 이동을 합니다.

• 위의 값과 같은 경우 : 문자가 달라서 위의 값과 왼쪽의 값 중 더 큰 값인 위의 값을 가져 온 경우
• 왼쪽 값과 같은 경우 : 문자가 달라서 위의 값과 왼쪽의 값 중 더 큰 값인 왼쪽의 값을 가져 온 경우
• 이 두가지를 제외한 경우 : LCS 누적이 일어난 부분, 해당 부분의 알파벳을 Stack에 저장 대각선 방향으로 이동

수가 변한다는 것은 해당 부분 LCS 누적이 일어난 부분이기 때문에 대각선으로 이동하여 다음 LCS를 찾아야합니다.

 

여기서 Stack에 저장하는 이유는 값을 거꾸로 탐색을 하기 때문에 Stack의 FILO(First In Last Out)의 후입선출 방식을 이용해 수열의 순서를 맞추는 것이다.

 

여기서 Stack에 들어가는 부분은 노란색으로 색칠된 부분에 해당하는 i 인덱스의 String2 의 값이다.

 

 

<전체코드>

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();
        
        int len1 = string1.length;
        int len2 = string2.length;
        
        LCS = new int[len2 + 1][len1 + 1];
        
        for(int i = 1; i < len2 + 1; i++) {
        	
        	for(int j = 1; j < len1 + 1; j++) {
        		
        		if(string2[i - 1] != string1[j - 1])
        			LCS[i][j] = Math.max(LCS[i][j-1], LCS[i -1][j]);
        		else
        			LCS[i][j] = LCS[i-1][j-1] + 1;
        	}
        }
        
        sb.append(LCS[len2][len1] + "\n");
        
        int i = len2, j = len1;
        Stack<Character> stack = new Stack<>();
        
        while(i >= 1 && j >= 1) {
        	if(LCS[i][j] == LCS[i-1][j])
        		i--;
        	
        	else if( LCS[i][j] == LCS[i][j-1])
        		j--;
        	
        	else {        		
        		stack.push(string2[i-1]);
        		i--;
        		j--;
        	}
        }
        
        while(!stack.isEmpty())
        	sb.append(stack.pop());
                
        System.out.println(sb);
    }
        
}