1 분 소요

문제

문제 바로가기

입력

첫째 줄과 둘째 줄에 두 문자열이 주어진다. 문자열은 알파벳 대문자로만 이루어져 있으며, 최대 1000글자로 이루어져 있다.

출력

첫째 줄에 입력으로 주어진 두 문자열의 LCS의 길이를, 둘째 줄에 LCS를 출력한다.

LCS가 여러 가지인 경우에는 아무거나 출력하고, LCS의 길이가 0인 경우에는 둘째 줄을 출력하지 않는다.

접근방법

LCS는 최장 공통 부분 수열(Longest Common Subsequence) 의 약자이다.

주어진 두 문자열에서 공통으로 등장하는 부분 문자열 중 가장 긴 것을 찾는 알고리즘이다.


배열d[][]를 표로 나타내면 다음과 같다.

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


두 문자열의 각각의 문자를 비교한다.

만약 두 문자가 같다면 d[i][j] = d[i-1][j-1] + 1

두 문자가 다르다면 d[i][j] = Math.max(d[i][j-1], d[i-1][j]) 이 된다.

최종적으로 배열d[][]의 마지막 원소가 두 문자열의 LCS 길이가 된다.

LCS의 문자열은 스택을 이용해 역추적으로 찾아낼 수 있다.

풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

class Coo {
    char c; // 두 문자열에서 공통으로 등장한 문자
    int n;  // 현재까지 찾은 최대 공통 부분 문자열의 길이
    int x, y; // 현재까지 찾은 최대 공통 부분 문자열의 끝 위치
    Coo(char c, int n, int x, int y) {
        this.c = c;
        this.n = n;
        this.x = x;
        this.y = y;
    }
}
public class Main {
    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 n = str1.length();
        int m = str2.length();
        int[][] d = new int[n+1][m+1];
        List<Coo> temp = new ArrayList<>();

        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= m; j++) {
                if(str1.charAt(i-1) == str2.charAt(j-1)) {
                    d[i][j] = d[i-1][j-1] + 1;
                    temp.add(new Coo(str1.charAt(i-1), d[i][j], i, j));
                }
                else {
                    d[i][j] = Math.max(d[i][j-1], d[i-1][j]);
                }
            }
        }

        System.out.println(d[n][m]);

        if(d[n][m] != 0) {
            Stack<Character> stack = new Stack<>();
            int common = d[n][m];
            int tx = -1;
            int ty = -1;
            for (int i = temp.size() - 1; i >= 0; i--) {
                if (temp.get(i).n == common && temp.get(i).x != tx && temp.get(i).y != ty) {
                    stack.push(temp.get(i).c);
                    common--;
                    tx = temp.get(i).x;
                    ty = temp.get(i).y;
                }
            }

            while (!stack.isEmpty()) {
                System.out.print(stack.pop());
            }
        }
    }
}

댓글남기기

참고