백준 17218번: 비밀번호 만들기

문제 설명

• https://www.acmicpc.net/problem/17218
• 최장 공통 부분수열(LCS)의 결과값을 출력하는 문제입니다.

접근법

• 최장 공통 부분수열은 최장 공통 문자열에서부터 시작합니다. 최장 공통 문자열의 pseudocode는 다음과 같습니다.

if(s1.charAt(i) == s2.charAt(j)) {
	dp[i][j] = dp[i-1][j-1]+1;
}else {
	dp[i][j] = 0;
}

• 최장 공통 부분수열의 pseudocode는 다음과 같습니다.

if(s1.charAt(i) == s2.charAt(j)) {
	dp[i][j] = dp[i-1][j-1]+1;
}else {
	dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
}

(i,j)는 s1의 i까지와 s2의 j까지를 비교하는 겁니다. 만약 s1이 "abcd" s2가 "efghi"라면 (2,3)은 ab와 efg를 비교하는 겁니다.
이때 ab와 efg를 비교하는 건 두 가지 측면에서 생각할 수 있습니다.

1. a와 efg를 비교하고 있었는데 b가 추가됐다.
2. ab와 ef를 비교하고 있었는데 g가 추가됐다.

최장 공통 문자열은 문자가 연속해야 하기 때문에 i번째와 j번째의 값이 다르면 바로 0이 됩니다. 하지만 최장 공통 부분수열은 나중에 값이 증가할 가능성이 있기 때문에 그 값을 계속 보존해야 합니다. 즉 s1.charAt(i)!=s2.charAt(j)일 때 (i,j)문자열을 만드는 방법은 두 가지가 있는데 우리는 최장 공통 부분수열을 구해야 하기 때문에 두 방법 중 이전까지 만들어둔 최장 공통 부분수열의 길이가 더 긴 값을 취해야 합니다.

• 역추적
  위 최장 공통 부분수열의 pseudocode를 바탕으로 값을 역추적할 수 있습니다.
  dp[i-1][j]와 dp[i][j-1] 둘 중 어떤 하나의 값이 dp[i][j]와 같다면 이는 s1.charAt(i)!=s2.charAt(j)라는 의미입니다. 반대로 dp[i-1][j]와 dp[i][j-1]의 값이 모두 dp[i][j]와 다르다면 이는 s1.charAt(i)==s2.charAt(j)이라는 의미이고, 이 값이 최장 공통 부분수열에 포함된다는 의미입니다.

정답

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

public class Main {
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String s1 = br.readLine();
		String s2 = br.readLine();
		int N = s1.length();
		int M = s2.length();

		// LCS의 길이를 찾는 dp
		int[][] dp = new int[N+1][M+1];
		for (int i = 1; i <= N; i++) {
			for (int j = 1; j <= M; j++) {
				if(s1.charAt(i-1) == s2.charAt(j-1)) {
					dp[i][j] = dp[i-1][j-1]+1;
				}else {
					dp[i][j] = Math.max(dp[i-1][j],dp[i][j-1]);
				}
			}
		}
        
        // 결과값 역추적
		StringBuilder sb = new StringBuilder();
		int cnt = dp[N][M];
		int row = N;
		int col = M;
		while(cnt>0) {
			if(dp[row-1][col] == cnt) {
				row--;
			}else if(dp[row][col-1] == cnt) {
				col--;
			}else {
				sb.append(s1.charAt(row-1));
				cnt--;
				row--;
				col--;
			}
		}
		System.out.println(sb.reverse().toString());
//		for (int i = 0; i < dp.length; i++) {
//			System.out.println(Arrays.toString(dp[i]));
//		}
		
	}
}