[백준] 9252번 - LCS 2 [Java]

https://www.acmicpc.net/problem/9252

 

[백준] 9252번 - LCS 2 [Java]

[백준] 9252번 - LCS 2 [Java]

---

1.  아이디어

 

이전 LCS 문제에서 실제 문자열 출력이 추가된 문제로 LCS를 구했던 규칙을 통해 dp 배열을 거슬러가며 실제 문자열을 구할 수 있다.([코딩테스트 준비/백준] - [백준] 9251번 - LCS [Java])

---

2. 문제풀이

 

기존 dp 배열에서 실제 LCS에 포함되는 문자열인 경우 dp[i-1][j-1] + 1로 dp 배열을 갱신했었다. 이를 활용해서 dp 배열의 끝에서 두 포인터를 r, c를 배치하고 출발시켜서 dp[r-1][c] 또는 dp[r][c-1]과 dp[r][c]가 같은 경우 해당 위치는 LCS를 이루지 못했던 경우이므로 해당 위치로 이동하고 dp[r-1][c] 와 dp[r][c-1] 와 다를 경우 해당 위치는 LCS를 만들었던 위치이므로 선택한 후 r-1, c-1로 이동한다.

역순으로 추적하므로 이를 Stack에 넣은 후 출력하는 방식으로 구현했다.

---

3. 코드

 

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

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

        char[] str1 = br.readLine().toCharArray();
        char[] str2 = br.readLine().toCharArray();

        int N = str1.length;
        int M = str2.length;

        int[][] dp = new int[1 + N][1 + M];

        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= M; j++) {
                if (str1[i - 1] == str2[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]);
            }
        }

        sb.append(dp[N][M]).append("\n");

        Deque<Character> stack = new ArrayDeque<>();
        int r = N;
        int c = M;

        while (!(r == 0 || c == 0)) {
            if (dp[r][c] == dp[r - 1][c]) {
                r--;
            } else if (dp[r][c] == dp[r][c - 1]) {
                c--;
            } else {
                stack.push(str1[r - 1]);
                r--;
                c--;
            }
        }

        while (!stack.isEmpty()) {
            sb.append(stack.pop());
        }

        bw.write(sb.toString());
        bw.flush();
    }
}

---

4. 후기