문제 링크

성능 요약

메모리: 18968 KB, 시간: 136 ms

분류

다이나믹 프로그래밍, 문자열

제출 일자

2025년 1월 4일 20:15:55

문제 설명

LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다.

예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다.

입력

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

출력

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

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

풀이

• 이전에 풀었던 LCS와 차이가 없는 것 같다..
• 당시에는 방법을 몰라서 풀이를 찾아보고 참고했지만, 이번에는 스스로 풀 수 있었다.
• 인덱스 오타를 조심해야한다.. 디버깅 어렵다..

설계 : 5분

• 최대공통부분수열을 구하는 다이나믹 프로그래밍 알고리즘을 사용했다.
• 2차원 dp테이블에 첫 단어의 i번째, 두번째 단어의 j번째까지 비교했을때 최대공통부분수열 길이를 저장한다.
• 비교하는 두 문자가 같은 경우 [i-1][j-1]의 최대공통부분수열 길이에 +1 한 수를 저장한다.
• 다를 경우에는 [i][j-1]과 [i-1][j] 중 더 큰 수를 끌어와 저장한다.

코드(Java)

• 구현 시간: 30분

/**
 * Author: yngbao97, Yuk Yejin
 * Problem: LCS 2_9252
 * Date: 2025.01.04
 */

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

public class Main {
	static BufferedReader br;
	static BufferedWriter bw;
	static StringTokenizer st;

	public static void main(String[] args) throws Exception {

		br = new BufferedReader(new InputStreamReader(System.in));
		bw = new BufferedWriter(new OutputStreamWriter(System.out));

        char[] A = br.readLine().toCharArray();
        char[] B = br.readLine().toCharArray();
        int[][] lcs = new int[A.length+1][B.length+1];

        for (int i = 0; i < A.length; i++) {
            for (int j = 0; j < B.length; j++) {
                if (A[i] == B[j]) lcs[i+1][j+1] = lcs[i][j] + 1;
                else lcs[i+1][j+1] = Math.max(lcs[i][j+1], lcs[i+1][j]);
            }
        }

        Stack<Character> word = new Stack<>();
        int i = A.length-1;
        int j = B.length-1;

        while (i >= 0 && j >= 0) {
            if (A[i] == B[j]) {
                word.push(A[i]);
                i--;
                j--;
            } else {
                if (lcs[i+1][j] >= lcs[i][j+1]) j--;
                else i--;
            }
        }

        bw.write(String.valueOf(word.size()) + "\n");
        while (!word.isEmpty()) bw.write(word.pop());
		bw.flush();
		bw.close();
		br.close();
	}
}