[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();

    }
}