[백준] 9251. LCS

문제

 

풀이

하루종일 이 문제만 붙들고 있었던 것 같다. 처음 시도했던 방법은 일차원 배열을 통해 메모이제이션을 수행하고자 했다. 하지만 일차원 배열을 사용하는 경우에는 같은 문자가 여러번 등장할 경우에 대해서 잘못된 최대값을 얻는 경우가 발생한다.

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

public class Main {
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

	static int[][] cache;

	public static void main(String[] args) throws IOException {
		String s1 = br.readLine();
		String s2 = br.readLine();
		boolean isS1 = (s1.length() < s2.length()) ? true : false;
		int len = (s1.length() < s2.length()) ? s1.length() : s2.length();
		cache = new int[len + 1][2];

		if (isS1) {
			System.out.println(getLCS(s1, s2, len));
		} else {
			System.out.println(getLCS(s2, s1, len));
		}
	}

	static int getLCS(String smaller, String longer, int len) {
		cache[len][0] = 0;
		cache[len][1] = len-1;
		for (int i = len - 1; i >= 0; i--) {
			char target = smaller.charAt(i);
			int maxCnt = 0;
			int maxIdx = -1;
			for (int j = i + 1; j <= len; j++) {
				int idx = longer.substring(0, cache[j][1] + 1).lastIndexOf(target);
				if (idx < 0)
					continue;
				if (maxCnt < cache[j][0] + 1) {
					maxCnt = cache[j][0] + 1;
					maxIdx = idx;
				} else if (maxCnt == cache[j][0] + 1) {
					maxIdx = (maxIdx < idx) ? idx : maxIdx;
				}
			}
			cache[i][0] = maxCnt;
			cache[i][1] = maxIdx;
		}
		
		int max = Integer.MIN_VALUE;
		for (int i = 0; i < len; i++) {
			if (max < cache[i][0])
				max = cache[i][0];
		}
		return max;
	}
}

그래서 모든 경우의 수를 알 수 있기 위해서 이차원 배열을 통해 메모이제이션을 생각했다. 이차원으로 수행하는 경우, 각 자리까지의 최대 LCS를 유지하는 방식으로 메모이제이션을 수행해야한다. 좀 더 자세히 보면 만약 해당 자리와 같은 문자인 경우에는 이전의 그 자리까지 전의 최대값 + 1이 되고 만약 같지 않다면 이전 문자의 최대값(이전 행)과 이번 문자를 비교하면서 생긴 최대값(이전 열) 중에서 최대값이 된다.

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

public class Solution9251 {
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

	static int[][] cache;

	public static void main(String[] args) throws IOException {
		String row = br.readLine();
		String col = br.readLine();
		cache = new int [row.length() + 1][col.length() + 1];

		for (int i = 1; i < row.length() + 1; i++) {
			for (int j = 1; j < col.length() + 1; j++) {
				if (row.charAt(i - 1) == col.charAt(j - 1)) {
					cache[i][j] = cache[i-1][j-1] + 1;
				} else {
					cache[i][j] = Integer.max(cache[i-1][j], cache[i][j-1]);
				}
			}
		}
		System.out.println(cache[row.length()][col.length()]);
	}
}