[Algorithm] 백준 LCS 문제 - LCS 2(9252) 자바 풀이

안녕하세요. 회사와 함께 성장하고 싶은 KOSE입니다.

이번 포스팅은 백준 LCS 문제 - LCS2 자바 풀이를 진행하도록 하겠습니다.

문제 출처: https://www.acmicpc.net/problem/9252

9252번: LCS 2

 

1. 풀이 소스

 

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        String str1 = br.readLine(); // 문자열 1
        String str2 = br.readLine(); // 문자열 2
        int[][] dp = new int[str1.length() + 1][str2.length() + 1];

        for (int i = 1; i <= str1.length(); i++) { // LCS 공식
            for (int j = 1; j <= str2.length(); j++) {
                if (str1.charAt(i - 1) == str2.charAt(j - 1)) dp[i][j] = dp[i - 1][j - 1] + 1;
                else dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
            }
        }

        StringBuilder sb = new StringBuilder();
        if (dp[str1.length()][str2.length()] == 0) sb.append(0); // 만약 값이 0 -> LCS가 없음
        else {
            sb.append(dp[str1.length()][str2.length()]).append("\n");

            Stack<Character> stack = new Stack<>();
            int row = str1.length(), col = str2.length();
            while (row > 0 && col > 0) { // 역추적 --> LCS 공식에 따라, (행 - 1)과 같다면 행--, (열 - 1)과 같다면 열 --

                if (dp[row][col] == dp[row - 1][col]) row--;
                else if (dp[row][col] == dp[row][col - 1]) col--;
                else { // 행 혹은 열 하나씩 뺀 것과 같지 않다면, 나머지는 대각선
                    stack.push(str1.charAt(row - 1)); // 스택에 넣기
                    row--;
                    col--;
                }
            }

            while(!stack.isEmpty()) sb.append(stack.pop()); // 후입선출로 맨 마지막부터 출력
        }
        System.out.println(sb);
    }
}

 

2. 풀이 중점 사항 

 

LCS 공식 적용

 

for (int i = 1; i <= str1.length(); i++) { // LCS 공식
    for (int j = 1; j <= str2.length(); j++) {
        if (str1.charAt(i - 1) == str2.charAt(j - 1)) dp[i][j] = dp[i - 1][j - 1] + 1;
        else dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
    }
}

 

이전 LCS 문제에서 풀이했던 방식을 그대로 활용할 수 있습니다. 이전 블로그에서 자세하게 작성하였습니다. 혹시 LCS 공식이 헷갈리신다면 참고 부탁드립니다.!

https://gose-kose.tistory.com/119 

[Algorithm] 백준 LCS 문제 - LCS(9251) 자바 풀이

 

LCS 역추적하기

 

Stack<Character> stack = new Stack<>();
int row = str1.length(), col = str2.length();
while (row > 0 && col > 0) { // 역추적 --> LCS 공식에 따라, (행 - 1)과 같다면 행--, (열 - 1)과 같다면 열 --

    if (dp[row][col] == dp[row - 1][col]) row--;
    else if (dp[row][col] == dp[row][col - 1]) col--;
    else { // 행 혹은 열 하나씩 뺀 것과 같지 않다면, 나머지는 대각선
        stack.push(str1.charAt(row - 1)); // 스택에 넣기
        row--;
        col--;
    }
}

while(!stack.isEmpty()) sb.append(stack.pop()); // 후입선출로 맨 마지막부터 출력

 

LCS를 만들 때, 만약 두 문자열의 값이 같다면 대각선을 활용하고, 아니라면 행 혹은 열은 하나씩 줄여서 최대값으로 이어 가는 것을 확인할 수 있었습니다. 이를 그대로 활용하여, 최대값을 기준으로 대각선과 값이 같다면 stack에 값을 넣고, row, col을 각각 -- 해줍니다. 만약 행이 하나 작은 것과 같다면, 행을 줄이고, 열이 하나 작은 것과 같다면 열을 줄여서 최대값이 적용된 흐름대로 움직이는 것입니다.

 

이러한 방법으로 LCS의 값을 역추적할 수 있습니다. 이상으로 풀이를 마치겠습니다. 감사합니다!!!