[백준] 9251 LCS - Dynamic Programming (Java)

LCS (Longest Common Substring) 최장 공통 부분 문자열 문제 :

공통적으로 가지는 최장 문자열 구하기. 연속 되어야한다.

​

LCS (Longest Common Subsequence) 최장 공통 부분 수열 문제:

공통적으로 가지는 최장 부분 수열 구하기. 순서는 같아야 하며 연속되지 않아도 가능.

 

-

얼마전에 배운 global/local alignment의

max{

a[i-1][j-1] + match(mismatch)

a[i][j-1] + gap

a[i-1][j] + gap

}

에서 match 값을 1로, mismatch와 gap 값을 0으로 둔 셈.

---

(잠깐 alignment 정리하고 가기)

문자열을 비교하고 정렬하는 데 쓰이는 두 가지의 정렬 방법.

Global Alignment - Needleman-Wunsch

: 문자열 전체를 두고 gap을 사이사이 주면서 전체를 비교한다. 전체적인 동일성에 집중, 서열 전체를 비교하고 정렬하는 것.

​

Local Alignment - Smith-Waterman

: 부분적으로 유사한, 동일한 부분을 위주로 정렬.

​

GCATGCU와 GATTACA를 두었을 때 Global Alignment의 결과 중 하나는

GCATG-CU

G- ATTACA 가 됨.

Local Alignment의 경우는 AT가 되는 것.

 

출처 ㅣ https://blog.naver.com/sw4r/221115071239

출처 ㅣ https://blog.naver.com/sw4r/221115071239

import java.io.*;

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

		String str1 = br.readLine();
		String str2 = br.readLine();

		String arr[][] = new String[str1.length() + 1][str2.length() + 1];

		for (int i = 0; i <= str1.length(); i++) {
			for (int j = 0; j <= str2.length(); j++) {
				arr[i][j] = "0";
			}
		}

		localAlignment(arr, str1, str2);
		br.close();
	}

	public static void localAlignment(String arr[][], String str1, String str2) {
		int D = 0, U = 0, L = 0, max = 0;
		String dul = "";

		// 행렬 채우기
		for (int i = 1; i <= str1.length(); i++) {
			for (int j = 1; j <= str2.length(); j++) {
				if (str1.charAt(i - 1) == str2.charAt(j - 1)) // indexOf은 0에서부터 시작하므로
					D = getNum(arr[i - 1][j - 1]) + 1;
				else
					D = getNum(arr[i - 1][j - 1]) - 5; // mismatch 는 값을 아주 적게 주기 - 그냥 0으로 줘도 되는 듯.
				U = getNum(arr[i - 1][j]);
				L = getNum(arr[i][j - 1]);
				// match가 가장 중요하니까 gap 값은 그냥 주지 않아도 되는 것 같다(?)  - 알고보니 lcs 알고리즘이었음

				max = Math.max(D, U);
				max = Math.max(L, max);

				if (max == D) // go diagonally
					dul = "D";
				else if (max == U) // go up
					dul = "U";
				else if (max == L) // go left
					dul = "L";

				if (max < 0)
					max = 0;   // 이건 local alignment를 위한 거였는데 LCS에서는 마이너스가 나올 일이 없더라...

				arr[i][j] = max + dul;
			}
		}

		for (int i = 0; i <= str1.length(); i++) {
			for (int j = 0; j <= str2.length(); j++) {
				System.out.print(arr[i][j] + " ");
			}
			System.out.println();
		}

		// 최대값 구하기 ...max는 그냥 str1.length라고 해도 값은 잘 나온다. 그냥 끝에서 시작하던 말던 값은 잘 나옴.
		int maxi = 0;
		int maxj = 0;

		for (int i = 1; i <= str1.length(); i++) {
			for (int j = 1; j <= str2.length(); j++) {
				if (getNum(arr[maxi][maxj]) < getNum(arr[i][j])) {
					maxi = i;
					maxj = j;
				}
			}
		}

		System.out.println("max : arr " + maxi + " " + maxj + " = " + arr[maxi][maxj]);

		// 경로 찾기
		int result = 0;

		while (maxi != 0 && maxj != 0) {
			if (getWord(arr[maxi][maxj]).equals("D")) {  
           //대각선으로 내려온 경우 match이므로. mismatch는 값을 굉장히 작게 줬기에 max가 mismatch가 될 일이 없는 듯 하다
				result++;
				maxi--;
				maxj--;
			} else if (getWord(arr[maxi][maxj]).equals("U")) {
				maxi--;
			} else if (getWord(arr[maxi][maxj]).equals("L")) {
				maxj--;
			} else
				break;
		}

		System.out.println(result);

	}

	public static int getNum(String s) {
		if (s.length() >= 2)
			return Integer.parseInt(s.substring(0, s.length() - 1));
		else if (s.length() < 2)
			return Integer.parseInt(s.charAt(0) + "");
		else
			return 0;
	}

	public static String getWord(String s) {
		if (s.length() >= 2)
			return s.substring(s.length() - 1);
		return "";
	}
}