[백준,BOJ 9251] LCS(JAVA 구현,추가풀이)

 

-내 생각

  LIS알고리즘에 이은 LCS알고리즘이다. 전혀 처음 보는 유형의 문제였기 때문에 혼자 힘으로 풀지는 못했다.

 

-해법

  LCS의 경우 주의해야 할 경우가 Longest Common Subsequence인 최장 공통부분 순열이 있고, Logest Common Substring인 최장 공통부분 문자열인 경우가 있다고 한다. 순열의 경우는 현재 문제처럼 연속되는 문자는 고려하지 않고 단순히 두 문자열을 비교해서 겹치는 경우의 수를 구하는 것이다. 예를 들어 ACAYKP는 CAPCAK와 비교했을 때, A, C, P, K가 순서에 고려되지 않고 겹치게 된다. 그러나 문자열의 경우는 CA만이 순서와 내용이 일치한다는 차이점이 있다.

 

  LCS의 경우에는 2차원 배열을 이용해서 구하게 되는데 https://youtu.be/P-mMvhfJhu8 이곳에 2차원 배열을 채우는 방법에 대해서 설명이 되어있다. 이 내용에 대해서 이해해보고자 했는데, 결국 이해하지 못해서 일단 공식처럼 외우기로 했다. 주요한 내용은 두 문자열의 각 자리를 비교하여 일치할 경우 dp [i][j] = dp [i-1][j-1] +1이 되고, 일치하지 않을 경우는 dp [i][j] = Math.max(dp [i-1][j], dp [i][j-1])이 된다고 한다. 보통 이런 경우는 응용문제 나와버리면 탈탈 털리게 되는데.. 

 

import java.util.*;

public class Main {
	static String a,b;
	
	static int dp[][];
	
	
	public static void main(String[] args)   {
		Scanner sc = new Scanner(System.in);
		
		a=sc.nextLine();
		b=sc.nextLine();
		
		dp = new int[b.length()+1][a.length()+1]; // 각 문자열의 길이만큼 선언
        				// 주의해야 할 점은 무엇을 기준으로 무엇과 비교할지를 정한 후 순서에 맞게 선언해주어야 한다.
                        // 여기선 b를 기준으로 a와 비교하게 된다.
		
		for(int i=1;i<=b.length();i++) { // b를 기준으로
			
			for(int j=1;j<=a.length();j++) { // a와 비교
				
				if(b.charAt(i-1) != a.charAt(j-1)) { // 다를 경우
					
					dp[i][j] = Math.max(dp[i][j-1],dp[i-1][j]); //점화식
				}else { // 같을 경우
					dp[i][j] = dp[i-1][j-1]+1; // 점화식
				}
				
			}		
			
		}
		
		System.out.println(dp[b.length()][a.length()]); // 이곳 역시 선언과 똑같이 출력해주어야 런타임 에러가 나지 않는다.
		
		
		
		
	}
	
}

 

  +) 추가적으로 LCS의 길이가 아닌, LCS 자체를 구하는 경우 완성된 dp배열의 마지막 칸에서 다음과 같은 우선순위를 따라 이동하면 된다. 

  1) dp[n][n] != dp [i][j-1]

  2) dp [n][n]!= dp [i-1][j]

  3) dp [n][n]!= dp [i-1][j-1]

  즉, 왼쪽과 비교하여 다르면 이동, 같다면 위쪽과 비교하여 다르면 이동, 같다면 대각선과 비교하여 다르면 이동하면 각각의 열 값을 취해 입력받은 문자열을 이용해 출력하면 된다.

 

---

  LCS라는 문제를 푸는 방식에 대해서는 이해가 됐지만, 막상 따라 하면 못 짤 것 같다. ㅋㅋㅋㅋ 이해한 게 어디야

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		
		char[] str1 = in.nextLine().toCharArray();
		char[] str2 = in.nextLine().toCharArray();
		
		int[][] dp = new int[str1.length+1][str2.length+1];
		
		for(int i=1;i<=str1.length;i++) {
			for(int j=1;j<=str2.length;j++) {
				// 두 문자가 같다면, 대각선 전의 경우의 수에 해당 문자가 추가되는 경우이므로 +1
				if(str1[i-1] == str2[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]);
				}
			}
		}
		
		System.out.println(dp[str1.length][str2.length]);
		
		in.close();
	}

}