백준 9252 LCS 2 [자바]

in Develop / Solving

baekjoon 9252 LCS 2

java

문제 분석

  • 두 문자열이 주어진다. 문자열은 대문자로만 이루어져 있다.
  • 두 문잘열의 최장 공통 부분 수열을 구하고, 그 길이와 문자열을 나타내어라.

입력조건

String 문자열1
String 문자열2

풀이과정

  • dp

  • 각 문자열의 각 위치까지 최대인 공통 부분 수열을 계산하면서, 끝까지 진행.

  • 최초에 풀이를 진행할 때는 element라는 하나의 클래스를 만들어, 그 안에 현재 공통 부분 수열의 길이와, 그 문자열을 저장하였다.
  • 하지만 이렇게 진행하니 시간초과가 발생하였다.

  • 예상되는 원인으로는 1000*1000 사이즈의 문자열 배열을 계속 복사하니, 0.4초는 턱없이 부족했다고 생각한다.

  • 그래서, element 클래스를 날리고, 2차원 int 배열로 최장 공통 부분 수열의 길이만 저장하였고,

  • 이를 끝낸 후, 맨 끝에서부터 추적해서 올라가면서 정답 문자열을 만들었다.

  • 아래는 문제풀면서 그렸던 그림이다…

코드 구성

  • dp로 LCS 크기 저장하기

    for(int aidx = 1; aidx <= alen; aidx++) {
    for(int bidx = 1; bidx <= blen; bidx++) {
        if (a.charAt(aidx-1) == b.charAt(bidx-1)) map[aidx][bidx] = map[aidx-1][bidx-1] + 1;
        else map[aidx][bidx] = Math.max(map[aidx-1][bidx], map[aidx][bidx-1]);
    }
}
// dp 끝
System.out.println(map[alen][blen]);

  • 정답 문자열 찾기

    StringBuilder ans = new StringBuilder();
while(alen > 0 && blen > 0) {
    if(a.charAt(alen-1) == b.charAt(blen-1)) {
        ans.append(a.charAt(alen-1));
        alen--;
        blen--;
    }
    else {
        if(map[alen-1][blen] > map[alen][blen-1]) 
            alen--;
        else blen--;
    }
}

전체 코드

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

public class BJ9252_LCS2 {
	public static void main(String[] args) throws IOException, CloneNotSupportedException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String a = br.readLine();
		String b = br.readLine();
		
		int alen = a.length();
		int blen = b.length();
		int[][] map = new int[alen+1][blen+1];
		
		for(int aidx = 1; aidx <= alen; aidx++) {
			for(int bidx = 1; bidx <= blen; bidx++) {
				if (a.charAt(aidx-1) == b.charAt(bidx-1)) map[aidx][bidx] = map[aidx-1][bidx-1] + 1;
				else map[aidx][bidx] = Math.max(map[aidx-1][bidx], map[aidx][bidx-1]);
			}
		}
		// dp 끝
		System.out.println(map[alen][blen]);
		
		// 디버그
//		for(int i = 1; i <= alen; i++) {
//			for(int j = 1; j <= blen; j++) {
//				System.out.print(map[i][j] + " ");
//			}
//			System.out.println();
//		}
		
		StringBuilder ans = new StringBuilder();
		while(alen > 0 && blen > 0) {
			if(a.charAt(alen-1) == b.charAt(blen-1)) {
				ans.append(a.charAt(alen-1));
				alen--;
				blen--;
			}
			else {
				if(map[alen-1][blen] > map[alen][blen-1]) 
					 alen--;
				else blen--;
			}
		}
		if(!ans.equals("")) System.out.print(ans.reverse());
	}
}

PS

시간초과를 받은 코드

package ChangHangeol;

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

public class BJ9252_LCS2 {
	static class element implements Cloneable {
		int len;
		String data;
		element(int len, String data){
			this.len = len;
			this.data = data;
		}
		@Override
		protected element clone() throws CloneNotSupportedException {
			return (element) super.clone();
		}
	}
	public static void main(String[] args) throws IOException, CloneNotSupportedException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String a = br.readLine();
		String b = br.readLine();
		
		int alen = a.length();
		int blen = b.length();
		
		element[][] map = new element[alen+1][blen+1];
		for(int i = 0; i <= blen; i++) map[0][i] = new element(0, "");
		for(int i = 0; i <= alen; i++) map[i][0] = new element(0, "");
		
		for(int aidx = 1; aidx <= alen; aidx++) {
			for(int bidx = 1; bidx <= blen; bidx++) {
				element idf1 = map[aidx][bidx-1];
				element idf2 = map[aidx-1][bidx];

				if(idf1.len > idf2.len) map[aidx][bidx] = idf1.clone();
				else					map[aidx][bidx] = idf2.clone();
				
				if(a.charAt(aidx-1) == b.charAt(bidx-1)) {
					element idf = map[aidx-1][bidx-1];
					if (map[aidx][bidx].len < idf.len + 1)
						map[aidx][bidx] = new element(idf.len + 1, String.format(idf.data + b.charAt(bidx-1)));
				}
			}
		}
		element f = map[alen][blen];
		System.out.println(f.len + "\n" + f.data);
	}
}