백준 9252번 LCS2(JAVA)

문제

9252번: LCS 2

 

풀이

import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        String s1 = br.readLine();
        String s2 = br.readLine();

        int mx = s1.length();
        int my = s2.length();

        int[][] map = new int[mx + 1][my + 1];

        for (int i = 1; i < map.length; i++) {
            for (int j = 1; j < map[i].length; j++) {
                if (s1.charAt(i - 1) == s2.charAt(j - 1)) { // 같은 문자일 때 왼쪽 대각선 위 값에 1을 더해준다.
                    map[i][j] = map[i - 1][j - 1] + 1;
                } else { // 같은 문자가 아닐 때는 바로 위나 왼쪽 값의 최댓값을 선택한다.
                    map[i][j] = Math.max(map[i - 1][j], map[i][j - 1]);
                }
            }
        }

        // 연속 문자열이 아니고 공통 부분 수열이므로 값이 누적되어 있다. 따라서 맨 오른쪽 밑부터 탐색해도 무방하다.
        while (mx != 0 && my != 0) {
            // 첫번째나 두번째 조건문에서 true가 생기면 해당 문자는 일치하는 것이 아님을 알 수 있다.
            if (map[mx][my] == map[mx - 1][my]) { 
                mx -= 1;
            } else if (map[mx][my] == map[mx][my - 1]) {
                my -= 1;
            } else {
                sb.append(s1.charAt(mx - 1));
                mx -= 1;
                my -= 1;
            }
        }

        if (sb.length() != 0) {
            System.out.print(sb.length() + "\n" + sb.reverse());
        } else {
            System.out.print(sb.length());
        }
    }
}

 

	-	A	C	A	Y	K	P
-	0	0	0	0	0	0	0
C	0	0	1	1	1	1	1
A	0	1	1	1	2	2	2
P	0	1	2	2	2	3	3
C	0	1	2	2	2	3	3
A	0	1	2	2	2	3	4
K	0	1	2	3	3	3	4

맨 오른쪽 아래 칸(4)부터 문자를 찾아나가는 과정은 위와 같다. 쉽게 생각해서 값이 누적되었던 경로를 거꾸로 추적해서 따라가는 것이다. 문자가 같지 않을 때는 위나 아래 중 큰 값을 채택하여 썼다. 따라서 바로 위 칸이나 왼쪽 칸 중 현재 칸의 값과 동일한 값을 가진 칸을 찾아 이동하는 것이다. 단순히 같은 값을 가진 칸으로 이동했을 때는 문자를 기록하지 않고, 더 작은 값의 칸으로 이동했을 때는 문자를 기록하면 된다. 최종적으로는 찾아야 하는 공통 부분 문자열의 뒤집어진 값을 얻게 되니 뒤집어서 출력하기만 하면 된다.