[BOJ] LCS 2(9252)

[백준(BOJ)] 9252_LCS 2 JAVA

문제 : BOJ_9252번 LCS 2

문제 설명

두 개의 문자열이 있고, 그 문자열의 공통부분 수열 중 가장 긴 수열을 찾는 것이다.

기존의 LCS 문제와 다른 점은 수열의 길이뿐만 아니라 수열이 어떤 문자열인지 출력해야 한다.

---

Solution

DP

dp[i][j] = 첫 번째 문자열의 인덱스가 i, 두 번째 문자열의 인덱스가 j 일 때 공통부분 수열의 최댓값

이라고 정의하자.

첫 번째 문자열의 i 번째 문자와 두 번째 문자열의 j 번째 문자가 같다면,

dp[i][j] = dp[i-1][j-1] + 1로 dp 값을 할당한다.

i와 j의 이전 하나 이전 인덱스의 dp 값에서 두 문자가 같다면 공통부분 수열의 길이가 늘어나므로 1을 더해주는 식이다.

첫 번째 문자열의 i 번째 문자와 두 번째 문자열의 j 번째 문자가 다르다면,

dp[i][j]는 dp[i][j-1], dp[i-1][j] 중 최댓값이 성립한다.

찾고자 하는 i, j의 dp 값에서 첫 번째 문자열의 i 번째 문자를 확인하기 전 or 두 번째 문자열의 j 번째 문자를 확인하기 전 중의 최댓값을 dp에 할당하는 것이다.



여기까지는 기존의 문제와 같으며, lcs 문자열을 출력하기 위해 기존에 int형 배열이 아닌, int 필드와 String 필드를 가지고 있는 클래스(class Node)를 선언하여 해결했다.

두 문자가 같은 경우엔 값도 1 추가해 주지만, String에 해당 문자열도 더해주면서 마지막에 최종 문자열도 출력해 준다.

---

Description

• nodes[i][j] = new Node(0, "")로 모든 Node 값을 선언 및 초기화해 주었다.
• i, j 번째의 최종 값은 nodes[i][j]가 아닌 nodes[i+1][j+1]에 넣어주었다.

---

소스 코드

import java.io.*;

class Node{
    private int val;
    private String str;
    public Node(int val, String str){
        this.val = val;
        this.str = str;
    }

    public void setStr(String str) {
        this.str = str;
    }

    public void setVal(int val) {
        this.val = val;
    }

    public int getVal() {
        return val;
    }

    public String getStr() {
        return str;
    }
}

public class Main {
    public static String str1, str2;
    public static int n,m;
    public static Node[][] nodes;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        str1 = br.readLine();
        str2 = br.readLine();
        n = str1.length();
        m = str2.length();
        nodes = new Node[n+1][m+1];
        for(int i=0; i<=n; i++){
            for(int j=0; j<=m; j++){
                nodes[i][j] = new Node(0,"");
            }
        }

        for(int i=0; i<n; i++){
            for(int j=0; j<m; j++){
                if (str1.charAt(i)==str2.charAt(j)){
                    nodes[i+1][j+1].setVal(nodes[i][j].getVal()+1);
                    nodes[i+1][j+1].setStr(nodes[i][j].getStr()+str1.charAt(i));
                }
                else{
                    if(nodes[i+1][j].getVal() >= nodes[i][j+1].getVal()){
                        nodes[i+1][j+1].setVal(nodes[i+1][j].getVal());
                        nodes[i+1][j+1].setStr(nodes[i+1][j].getStr());
                    }
                    else{
                        nodes[i+1][j+1].setVal(nodes[i][j+1].getVal());
                        nodes[i+1][j+1].setStr(nodes[i][j+1].getStr());
                    }
                }
            }
        }
        bw.write(String.valueOf(nodes[n][m].getVal())+"\n");
        bw.write(nodes[n][m].getStr()+"\n");
        bw.flush();
        br.close();
        bw.close();

    }
}