[BOJ/Java] 9251. LCS (최장 공통 부분 수열)

[BOJ/Java] 9251. LCS (최장 공통 부분 수열)

9251번: LCS

---

문제 해석

LCS 문제는 두 문자열이 주어졌을 때, 두 문자열 모두의 부분 수열이 되는 가장 긴 수열을 찾는 문제이다. 이 문제를 해결하기 위해 동적 프로그래밍(Dynamic Programming) 방식을 사용하며, 이를 구현하기 위한 점화식을 개발하고 코드로 옮겨야 한다.

풀이 과정

주어진 코드는 두 문자열 a와 b를 입력 받고, 이를 문자 배열로 변환한다. 이후, ans라는 2차원 배열을 사용하여 두 문자열 사이의 LCS 값을 저장한다. ans 배열의 각 요소는 a의 처음부터 i번째 문자와 b의 처음부터 j번째 문자까지의 LCS 길이를 나타낸다.

LCS() 메소드는 ans 배열을 채우는 로직을 포함하고 있다. 만약 a[i-1]와 b[j-1] 문자가 같다면, ans[i][j]는 ans[i-1][j-1] + 1이 된다. 즉, 이전 문자까지의 LCS 길이에 현재 일치하는 문자 하나를 추가하는 것이다. 문자가 다르다면, ans[i][j]는 ans[i-1][j]와 ans[i][j-1] 중 더 큰 값을 선택한다. 이는 현재 문자를 무시하고 최대 LCS 길이를 유지하기 위함이다.

코드

package edu.ssafy.im.BOJ.Gold.G5.No9251;

import java.io.*;

public class Main {
    private static char[] b;
    private static char[] a;
    private static int[][] ans;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();

        a = br.readLine().toCharArray();  // 첫 번째 문자열을 문자 배열로 변환
        b = br.readLine().toCharArray();  // 두 번째 문자열을 문자 배열로 변환
        ans = new int[a.length + 1][b.length + 1];  // LCS 길이를 저장할 2차원 배열 초기화

        sb.append(LCS());  // LCS 계산 결과를 StringBuilder에 추가
        bw.write(sb.toString());  // 결과 출력
        bw.flush();  // 버퍼 비우기
        bw.close();  // 스트림 닫기
    }

    private static int LCS() {
        for (int i = 1; i < ans.length; i++) {
            for (int j = 1; j < ans[0].length; j++) {
                if (a[i - 1] == b[j - 1]) ans[i][j] = ans[i - 1][j - 1] + 1;  // 문자가 일치하는 경우
                else ans[i][j] = Math.max(ans[i - 1][j], ans[i][j - 1]);  // 문자가 일치하지 않는 경우
            }
        }

        return ans[a.length][b.length];  // 최종 LCS 길이 반환
    }
}

시간 복잡도 분석

이 알고리즘의 시간 복잡도는 O(m * n)이다, 여기서 m과 n은 각각 문자열 a와 b의 길이이다. 각 문자에 대해 나머지 문자열의 각 문자를 한 번씩 비교하기 때문에, 두 문자열의 길이를 곱한 값이 곧 연산 횟수가 된다.

느낀점

동적 프로그래밍을 이용해 LCS 문제를 해결하는 방식은 초기에 이해하기 어렵지만, 한 번 로직을 이해하면 다양한 문자열 처리 문제에 적용할 수 있다는 점에서 매우 유용하다. 이 문제를 통해 점화식 설정과 배열을 사용한 상태 저장의 중요성을 다시 한번 느낄 수 있었다.