[알고리즘/자바] 백준 9252번 - LCS 2

 

 

 

9252번: LCS 2

 

처음에 LCS를 푸는 알고리즘을 모르고 접근했다가 한참 고생했다.

 

아래는 처음에 접근한 방식.

입력으로 문자열 2개가 주어지는데 이를 n1, n2라고했다.

n1의 첫번째 문자를 잡고 n2를 처음부터 순회한다. n2에 일치하는 문자가 있다면 정지하고 n1의 두번째 문자를 잡고 n2를 정지한 부분에서 부터 시작한다. 이 방식으로 n2도 똑같이 진행한다. 

 

위에서 생각한 방식으로 구현한 소스코드. 

2중 for문을 사용했다. dp를 쓰지않아 시간초과가 나올것으로 예상했는데 "틀렸습니다"가 나왔다. 

		String ans1 = "";
		int s=0;
		for(int i=0; i<n1.length; i++) {
			for(int j=s; j<n2.length; j++) {
				if(n1[i].equals(n2[j])) {
					ans1 += n1[i];
					s =j+1;
					break;
				}
			}
		}
		
		s=0;
		String ans2 = "";
		for(int i=0; i<n2.length; i++) {
			for(int j=s; j<n1.length; j++) {
				if(n2[i].equals(n1[j])) {
					ans2 += n2[i];
					s =j+1;
					break;
				}
			}
		}

 

위 소스코드는 ACDEB , BCDEA 두 문자열이 입력으로 나왔을때 틀립 답을 구한다.

 

n1의 첫번째 문자 A로 n2를 검사하면 n2의 마지막 문자인 A와 만나게 된다. 이렇게 되면 n1의 두번째문자인 C는 비교할 기회조차 얻지 못하고 for문이 종료되어버리고 만다.  위 소스코드에서 n1의 두번째 문자인 C도 비교를 수행하기 위해선 for문이 한 개 더 필요할것이다. 

 

여기서 고민을 하다가 도저히 풀이가 생각이 안나서 LCS 알고리즘을 공부했다. 아래는 도움받은 유튜브 영상. 

 

 

위 영상에서도 설명하듯이 문자열 간의 부분수열을 비교하기 위해서 2차원 테이블 형태로 데이터를 처리해야한다. 

{ A, C, D, E, B }와 { B, C, D, E, A }를 이용해 테이블을 채우자.

 

 

위 테이블에서 파란색 셀의 0이 의미하는것은 {B} 와 {A}의 LCS의 길이이다.( = 0)

 

 

.

위 테이블에서 파란색 셀의 0이 의미하는것은 {B} 와 {A,C}의 LCS의 길이이다.( = 0 )

 

 

 

위 테이블에서 파란색이 의미하는 것은 {B}와 {A,C,D,E,B}의 LCS의 길이이다. ( = 1 )

 

 

 

위 테이블에서 파란색 셀이 의미하는것은 {B,C,D} 와 {A,C,D}의 LCS의 길이다. ( = 2 )

 

 

이런 테이블을 몇개 그리다 보면 규칙이 보인다.

 

 

초록색 셀끼리 비교할때 문자가 서로 다르다면 파란색 셀에는 왼쪽값과 윗쪽 값을 비교해서 그냥 큰 수를 쓰면 된다. 

위 테이블에서 의미하는 파란색 셀의 윗쪽 값은 {B,C} 와 { A,C,D,E }의 LCS 길이이다.( = 1 )

위 테이블에서 의미하는 파라색 셀의 왼쪽 값은 {B,C,D}와 {A,C,D}의 LCS 길이이다.( = 2 )

따라서 파란색 셀은 길이가 더 긴 왼쪽값을 선택함으로써 {B,C,D}와 {A,C,D,E}의 LCS 길이를 가지게 된다( = 2 )

 

 

 

초록색 셀끼리 비교할때 문자가 서로 같다면 파란색 셀에는 왼쪽 위 대각선의 값에 +1을 해주면된다.

파란색 셀에  {B,C,D,E} 와 {A,C,D,E}의 LCS 길이인 3을 기록한다.

 

 

 

이런식으로 하면 LCS의 길이를 구할 수 있다.

 

 

 

LCS 2 문제는 여기서 길이가 아닌 LCS에 해당하는 부분수열을 구해야 한다. 위에서 2개의 룰이 있었는데

첫번째가 문자끼리 비교했을때 다르면 셀의 좌측과 윗쪽 값중 큰값을 선택.

두번째가 문자끼리 비교했을때 같으면 셀의 대각선 왼 쪽 위의 값 + 1.

 

위 룰을 이용해서 가장 마지막 셀에서 다시 역추적 하면 된다. 

가장 마지막 셀(주황색)부터 추적을 시작한다. 해당 셀의 문자 K, P로 일치 하지 않으므로 좌측과 위 값중 가장 큰값을 선택한다. 셀의 문자가 일치하면 왼쪽 대각선 위로 이동하며 일치 하는 문자를 기록한다. 이런식으로 위 테이블 처럼 쭉 추적을 셀의 값이 0이 되는 순간 추적을 중단한다.

 

위와 똑같은 행위를 문자 비교없이 테이블의 값만으로 수행할 수가 있다. 주황색 셀이 좌측과 윗쪽의 값을 봤더니 4가 존재한다. 이는 주황색 셀은 {C,A,P,C,A,K} 와 {A,C,A,Y,K}에서  {C,A,P,C,A,K} 와 {A,C,A,Y,K,P} 로 P를 하나 추가한것에 불과하다는 뜻이다. LCS 길이에 변화를 줄 문자가 아니다라는뜻. 

 

 

 

위의 설명에 따라 주황색에서 초록색 셀로 포커싱을 이동한다.

초록색 셀은 왼쪽과 윗쪽 값과 같은 값이 없다. 이뜻은 대각선에서 +1이 되었다는 뜻이다. 대각선에서 더하기 1이 될때는 문자가 일치할때 밖에 없다. 따라서 해당 초록색 셀에 해당하는 문자는 LCS의 한 문자가 된다는 뜻이다. 

따라서 K를 출력한다. 이런식으로 추적하면 파란색 셀을 따라갈 수 있고, 대각선 +1 되는 경우에만 문자를 출력하면 된다.

 

 

 

위에서 설명한 내용을 소스코드로 작성했다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;


public class Main {
	
	
	static int[][] dp = new int[1001][1001];
	static String[] n1;
	static String[] n2;
			
	public static void main(String[] args) throws IOException{
		
		
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		
		n1 = br.readLine().split("");
		n2 = br.readLine().split("");
		String ans = solve();
		
		bw.write(ans.length() + "\n");
		if(ans.length()!=0 ) bw.write(ans + "\n");
		
		
		bw.flush();
		bw.close();
	}
	
	
	
	
	public static String solve() {
		
		// 테이블 그리기
		for(int i=0; i<n1.length; i++) {
			for(int j=0; j<n2.length; j++) {
				if(n1[i].equals(n2[j])) {
					dp[i+1][j+1] = dp[i][j]+1;
				}
				else {
					dp[i+1][j+1] = Math.max(dp[i+1][j], dp[i][j+1]);
				}
			}
		}
		
		int x = n1.length;
		int y = n2.length;
		String a = "";
		// 부분수열 구하기 시작
		while(x!=0 && y!=0) {
			
			if(n1[x-1].equals(n2[y-1])) {
				a +=n1[x-1];
			}
			
			if(dp[x-1][y] == dp[x][y]) { // 왼쪽값과 같다
				x-=1;
			} else if(dp[x][y-1] == dp[x][y]) { // 윗쪽값과 같다.
				y-=1;
			} else { // 왼쪽값과 윗쪽값과 같은 경우가 없다.
				x-=1;
				y-=1;
			}
		}
		
		String ans = "";
		for(int i=a.length()-1; i>=0; i--) {
			ans += a.charAt(i);
		}
		 
		
		return ans;
		
	}
	
	
	
		
}