[알고리즘][X] LCS 2

https://www.acmicpc.net/problem/9252

9252번: LCS 2

틀린 풀이

- lcs의 원리를 잘못 알고 있었다.

	private static int findLCSLength(char[] sequence1, char[] sequence2, int N, int M, int[][] dp) {
		for (int i = 1; i <= N; i++) {	
			for (int j = 1; j <= M; j++) {
				if (dp[i-1][j] == dp[i][j-1] && sequence1[i-1] == sequence2[j-1]) {
					dp[i][j] = dp[i][j-1] + 1;
				} else {
					dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
				}
			}
		}
		
		return dp[N][M];
	}

옳은 풀이

- 다음과 같이 서로 문자열이 같다면 현재의 원소에 대각선 왼쪽위의 값 + 1을 넣어준다.

	private static int findLCSLength(char[] sequence1, char[] sequence2, int N, int M, int[][] dp) {
		for (int i = 1; i <= N; i++) {	
			for (int j = 1; j <= M; j++) {
				if (sequence1[i-1] == sequence2[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]);
				}
			}
		}
		
		return dp[N][M];
	}

 

틀린 풀이

- 두번째 else if문에 문자열도 같다면이라는 조건을 추가해주면 맞다.

while (x>0 && y>0) {
			if (x == 0 || y == 0) {
				break;
			}
			
				if (dp[x-1][y] > dp[x][y-1]) {
					x -= 1;
				} else if (dp[x-1][y] < dp[x][y-1]) {
					y -= 1;
				} else if (dp[x-1][y] == dp[x][y-1]) {
					sb.append(sequence1[x-1]);
					x -= 1;
					y -= 1;
				} else {
					x -= 1;
				}
//			dp[x][y] == dp[x-1][y]인데 sequence의 값이 같을 수도 있지 않은가?
//			if (dp[x][y] == dp[x-1][y]) {
//				x--;
//			} else if (dp[x][y] == dp[x][y-1]) {
//				y--;
//			} else {
//				sb.append(sequence1[x-1]);
//				x--;
//				y--;
//			}
			}

옳은 풀이

while (x>0 && y>0) {
			if (x == 0 || y == 0) {
				break;
			}
			
				if (dp[x-1][y] > dp[x][y-1]) {
					x -= 1;
				} else if (dp[x-1][y] < dp[x][y-1]) {
					y -= 1;
				} else if (dp[x-1][y] == dp[x][y-1] && sequence1[x-1] == sequence2[y-1]) {
					sb.append(sequence1[x-1]);
					x -= 1;
					y -= 1;
				} else {
					x -= 1;
				}
//			
//			if (dp[x][y] == dp[x-1][y]) {
//				x--;
//			} else if (dp[x][y] == dp[x][y-1]) {
//				y--;
//			} else {
//				sb.append(sequence1[x-1]);
//				x--;
//				y--;
//			}
			}

옳은 풀이

- 이게 더 직관적이라고 생각한다.

- 왜냐하면 LCS 기법을 아예 반대로 추적하는 거기 때문이다.

while (true) {
			if (dp[x][y] == 0) {
				break;
			}
				if (sequence1[x-1] == sequence2[y-1]) {
					sb.append(sequence1[x-1]);
					x -= 1;
					y -= 1;
				} else if (dp[x-1][y] >= dp[x][y-1]) {
					x -= 1;
				} else if (dp[x-1][y] < dp[x][y-1]) {
					y -= 1;
				} 
				
			}

틀린 풀이

- 이렇게 하면 값이 제대로 나올 것이라 예상했으나 틀렸다고 나옴. 근데 디버깅이 불가능.

bw.write(lcs + '0');
bw.newLine();
if (lcs > 0) {
bw.write(sb.reverse().toString());
}
bw.close();

옳은 풀이

- int 값을 출력하고 싶다면 Integer.toString으로 바꾸자.

bw.write(Integer.toString(lcs));
bw.newLine();
if (lcs > 0) {
bw.write(sb.reverse().toString());
}
bw.close();

 

전체 풀이

package boj.solution9252;

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

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		char[] sequence1 = br.readLine().toCharArray();
		char[] sequence2 = br.readLine().toCharArray();
		int N = sequence1.length;
		int M = sequence2.length;
		
		int[][] dp = new int[N + 1][M + 1];
		
		int lcs = findLCSLength(sequence1, sequence2, N, M, dp);
		int x = N;
		int y = M;
		StringBuilder sb = new StringBuilder();
		
		while (true) {
			if (dp[x][y] == 0) {
				break;
			}
				if (sequence1[x-1] == sequence2[y-1]) {
					sb.append(sequence1[x-1]);
					x -= 1;
					y -= 1;
				} else if (dp[x-1][y] >= dp[x][y-1]) {
					x -= 1;
				} else if (dp[x-1][y] < dp[x][y-1]) {
					y -= 1;
				} 
				
			}
		
		bw.write(Integer.toString(lcs));
		bw.newLine();
		bw.write(sb.reverse().toString());
		bw.close();
	}
	private static void display(int[][] graph) {
		for (int i = 0 ; i < graph.length; i++) {
			for (int j = 0; j < graph[0].length; j++) {
				System.out.print(graph[i][j] + " ");
			}
			System.out.println();
		}
		
	}
	private static int findLCSLength(char[] sequence1, char[] sequence2, int N, int M, int[][] dp) {
		for (int i = 1; i <= N; i++) {	
			for (int j = 1; j <= M; j++) {
				if (sequence1[i-1] == sequence2[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]);
				}
			}
		}
		
		return dp[N][M];
	}
}