[백준]9251. LCS(Java, 자바)

문제

9251. LCS

📌 아이디어

LCS : Longest Common SubSequance

먼저 LCS란, 말 그대로 가장 긴(longest) 공통된(Common) 부분수열(subsequance)입니다.

두 문자열 중 공통되는 부분 문자열을 탐색해 그 길이를 반환하는 것이 문제의 핵심이였습니다. 처음에는 스택을 활용하여 LCS를 저장해 나가고자 했지만, 뜻대로 되지않아 DP를 활용하였습니다.

탐색 중 같은 문자라면 이전 DP 값에서 +1을 해주고, 그 외의 경우는 행과 열 중 MAX값을 확인하여 값을 최신화 해줍니다.

핵심 메소드

static int LCS(int[][] dp) {

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

	return dp[str1.length][str2.length];
}

📌 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class BOJ_9251 {
 
	static char[] str1;
	static char[] str2;
 
	static int[][] dp;
	
	static int LCS(int[][] dp) {

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

		return dp[str1.length][str2.length];
	}

	public static void main(String[] args) throws IOException{
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st1 = new StringTokenizer(br.readLine());
		StringTokenizer st2 = new StringTokenizer(br.readLine());
 
		str1 = st1.nextToken().toCharArray();
		str2 = st2.nextToken().toCharArray();
		
		dp = new int[str1.length+1][str2.length+1];
 
		System.out.println(LCS(dp));		
	}
}

피드백 및 개선점은 댓글을 통해 알려주세요😊