백준:9251 - LCS(Longest Common Subsequence, 최장 공통 부분 수열)

 

 

 

 

문제 개요

두개의 문자를 입력받는다. 

입력받은 문자열을 비교하여 두 문자열의 부분 수열이 되는 수열 중 가장 긴 수열의 길이를 구해 출력해주어야 한다.

 

 

 

풀이 방법을 생각하지 못해 도움을 받아 풀었다.

 

두 문자열을 비교해주어야 하니 행과 열에 문자열을 적어주고 하나씩 비교하며 길이를 적어주었다.

 

1. ACAYKP 와 C 비교 -> 처음 A와 비교했을 때는 일치하는 문자가 없기 때문에 0의 값이 들어가고 이후 C는 1개가 무조건 포함되므로 1이 들어간다.

2. ACAYKP 와 CA 비교 -> 위와 마찬가지 방식으로 적어주고 문자열에 CA가 포함된 순간 값이 1개 증가한다.

.

.

.

3.  ACAYKP 와 CAPCAK 비교 -> 두 문자열에서 가장 긴 수열의 길이는 ACAK로 4가 출력값이 된다.

 

 

해당 방식을 사용하여 Top-Down 방식과 Bottom-Up방식으로 코드를 구현해보자

 

Top-Down

 

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

public class Practice {

    static char[] str1;
    static char[] str2;
    static Integer[][] dp;

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

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String s1 = br.readLine();
        String s2 = br.readLine();

        str1 = s1.toCharArray(); //String 문자열을 char배열로 변환해준다.
        str2 = s2.toCharArray();

        dp = new Integer[str1.length][str2.length];

        System.out.println(Lcs(str1.length-1, str2.length-1));

    }

    public static int Lcs(int x, int y){
    //  인덱스의 범위가 0 보다 작은 숫자가 되는 순간을 고려해주어야 한다.
        if(x < 0 || y < 0){
            return 0;
        }

        if(dp[x][y] == null){
            if(str1[x] == str2[y]){
                dp[x][y] = Lcs(x-1, y-1) + 1;
            } else {
                dp[x][y] = Math.max(Lcs(x-1, y), Lcs(x, y-1));
            }
        }
        return dp[x][y];
    }
}

 

1. 문자열 입력받기
2. 입력받은 문자열을 한 글자씩 비교하기 위해 char배열로 변환
3. dp를 실행할 배열 선언
4. 재귀함수 Lcs 구현
   1. 재귀함수의 탈출조건은 인덱스 중 어느 하나라도 음수가 나오는 순간 종료가 되어야 하기 때문에 if 조건식을 만들어준다.
   2. 입력받은 인덱스의 dp배열값에 값이 없다면 2가지 조건을 실행시킨다.
      1. str[x] 의 문자와 str[y]의 문자가 같을때 이전 비교한 길이에 +1 을 해준다.
      2. 같지 않다면 이전 행의값과 이전열의 값을 비교하여 큰 값을 넣어준다.
5. 결과를 return 해준다.

 

Bottom-UP

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
 
public class Main {
 
	public static void main(String[] args) throws IOException {
 
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		char[] str1 = br.readLine().toCharArray();
		char[] str2 = br.readLine().toCharArray();
		
		int length_1 = str1.length;
		int length_2 = str2.length;
		
		// 공집합 표현을 위해 인덱스가 한 줄씩 추가 됨 
		int[][] dp = new int[length_1 + 1][length_2 + 1];
		
		// 1부터 시작 (index 0 은 공집합이므로 0의 값을 갖고있음) 
		for(int i = 1; i <= length_1; i++) {
			for(int j = 1; j <= length_2; j++) {
				
				// (i-1)과 (j-1) 번째 문자가 서로 같다면  
				if(str1[i - 1] == str2[j - 1]) {
					// 대각선 위 (i-1, j-1)의 dp에 +1 한 값으로 갱신 
					dp[i][j] = dp[i - 1][j - 1] + 1;	
				}
				
				// 같지 않다면 이전 열(i-1)과 이전 행(j-1)의 값 중 큰 것으로 갱신  
				else {
					dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
				}
			}
		}
		System.out.println(dp[length_1][length_2]);
		
	}
 
}

 

 

Top-Down 방식과 점화식 자체는 크게 차이가 없다

다른점은 인덱스를 1부터 시작해준다는 점과 Bottom부터 채워가기 때문에 null값과 인덱스의 범위가 벗어날때를 체크해주지 않아도 된다는 점이다.