백준 9252번 : LCS2 [자바]

 

 

 

🧫 문제 분석

 

✔️ 출처

LCS 2 골드 4

 

📖 문제

 

LCS 문제와 다른 점은  LCS를 출력해야한다는 것이다.

단순히 순차적으로 탐색하면서

LCS에서 길이가 1인 처음 만나는 문자

LCS에서 길이가 2인 처음 만나는 문자

이런식으로 풀면 안된다.  

 

문자열이 같은 문자가 연속으로 주어지는 경우 잘못된 LCS를 구하게 되기 때문이다. 

AAACCC
AACCA

 

  A A C C A
A 1 1 1 1 1
A 1 2 2 2 2 
A 1 2 2 2 3
C 1 2 3 3 3
C 1 2 3 4 4
C 1 2 3 4 4

 

이렇게 위에서부터 순차적으로 for문 탐색시 AAAC가 되버린다.

답은 AACC 이다.

 

때문에 가장 마지막 위치에서 이전 대각위, 왼쪽, 위쪽을 탐색하여 같은 길이 값이면 그 곳으로 이동하고

3곳이 다 다르다면 현재 자신이 LCS 문자가 맞다는 것이므로 알파벳을 저장하고 대각위쪽으로 이동한다. 

다음 탐색할 길이값은 현재 탐색 길이  값 - 1이다.

 

 

 

 

 

---

🔅 DFS

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.*;
import java.util.stream.IntStream;

public class Main {

    static int[][] LCS;
    static String str1;
    static String str2;
    static StringBuilder sb = new StringBuilder();
    // 대각 위 , 왼, 위
    static int[] dx = {-1, -1, 0};
    static int[] dy = {-1, 0, -1};
    
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        str1 = br.readLine();
        str2 = br.readLine();

        int str1Len = str1.length() + 1;
        int str2Len = str2.length() + 1;

        LCS = new int[str1Len][str2Len];


        for (int i = 1; i < str1Len; i++) {
            for (int j = 1; j < str2Len; j++) {
                if (str1.charAt(i - 1) == str2.charAt(j - 1)) {
                    LCS[i][j] = LCS[i - 1][j - 1] + 1;

                } else {
                    LCS[i][j] = Math.max(LCS[i - 1][j], LCS[i][j - 1]);
                }
            }
        }

        System.out.println(LCS[str1Len - 1][str2Len - 1]);

        dfs(str1Len - 1, str2Len - 1, LCS[str1Len - 1][str2Len - 1]);
        System.out.print(sb.reverse().toString());
    }



    private static void dfs(int r, int c, int length) {

        if (r < 0 || c < 0 || length <= 0) return;

        for (int i = 0; i < 3; i++) {
            int nextR = r + dy[i];
            int nextC = c + dx[i];

            if (nextR < 0 || nextC < 0) continue;

            // 같은 값을 가진 이전 위치가 존재한다면 그 위치로 이동
            if (length == LCS[nextR][nextC]) {
                dfs(nextR, nextC, length);
                return;
            }
        }

        sb.append(str1.charAt(r - 1));
        dfs(r - 1, c - 1, length - 1);


    }

}

 

🔅 반복문풀이

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

public class Main {


    // 대각 위 , 왼, 위
    static int[] dx = {-1, -1, 0};
    static int[] dy = {-1, 0, -1};


    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String str1 = br.readLine();
        String str2 = br.readLine();

        int str1Len = str1.length() + 1;
        int str2Len = str2.length() + 1;

        int[][] LCS = new int[str1Len][str2Len];

        for (int i = 1; i < str1Len; i++) {
            for (int j = 1; j < str2Len; j++) {
                if (str1.charAt(i - 1) == str2.charAt(j - 1)) {
                    LCS[i][j] = LCS[i - 1][j - 1] + 1;

                } else {
                    LCS[i][j] = Math.max(LCS[i - 1][j], LCS[i][j - 1]);
                }
            }
        }

        System.out.println(LCS[str1Len - 1][str2Len - 1]);

        int curR = str1Len - 1;
        int curC = str2Len - 1;
        int curLen = LCS[str1Len - 1][str2Len - 1];
        StringBuilder sb = new StringBuilder();

        while (curLen > 0) {
            boolean isNotEquals = true;

            for (int i = 0; i < 3; i++) {
                int nextR = curR + dy[i];
                int nextC = curC + dx[i];

                if (nextR < 0 || nextC < 0) continue;

                // 같은 값을 가진 이전 위치가 존재한다면 그 위치로 이동
                if (curLen == LCS[nextR][nextC]) {
                    curR = nextR;
                    curC = nextC;
                    isNotEquals = false;
                    break;
                }
            }

            // 같은 값을 가진 이전 위치가 존재하지 않다면 여기가 현재 길이의 최장 공통 길이 요소
            if (isNotEquals) {
                sb.append(str1.charAt(curR - 1));
                curR--;
                curC--;
                curLen--;
            }
        }

        System.out.print(sb.reverse().toString());
    }

}

 

 

❗ 오답노트 / 필요한 지식

1.