[BOJ] 백준 13711번 LCS4 (Java)

#13711 LCS4

난이도 : 골드 2

유형 : DP

13711번: LCS 4

▸ 문제

LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다.

예를 들어, [1, 2, 3]과 [1, 3, 2]의 LCS는 [1, 2] 또는 [1, 3] 이다. 

1부터 N까지 정수가 모두 한 번씩 등장하는 두 수열 A와 B가 주어졌을 때, 두 수열의 LCS 크기를 구하는 프로그램을 작성하시오.

▸ 입력

첫째 줄에 두 수열의 크기 N (1 ≤ N ≤ 100,000)이 주어진다.

둘째 줄에는 수열 A에 들어있는 수가, 셋째 줄에는 수열 B에 들어있는 수가 주어진다.

▸ 출력

두 수열의 LCS의 크기를 출력한다.

 

문제 풀이  

전에 풀었던 LCS3 문제와는 다르다. 

 

1958번 문제는 최대 길이가 100이라서 3중 포문을 돌려도 100*100*100 = 1,000,000번의 연산으로 시간복잡도에 문제가 없었다. 그런데 이 문제는 하나의 최대 길이가 100,000이라 2중 포문을 돌리면 10,000,000,000번 = 100억 연산으로 시간 초과가 발생한다. 그래서 문자열이아니라 숫자로 미리 주어진 것 같다.

 

이는 이진탐색으로 풀어야하는 문제이다. 해당 문제를 제대로 이해하고 싶으면 LIS2 문제를 풀고오자.

구상

문제의 조건을 보면 얼마나 친절하게 풀이를 하라고 줬는지 알 수 있다. 이전의 LCS1,2,3문제는 String으로 데이터를 주어졌지만 이 문제는 정수로 줬다. 동적 계획법으로 풀게되면 시간초과가 발생하니 이진탐색과 LIS를 활용하여 LCS를 풀어야한다.

 

두 수열의 크기는 N이고 수열에 들어가는 숫자는 1부터 N까지 정수가 한 번씩 모두 등장한다. 그러니깐 두 수열에 들어있는 숫자는 순서만 다르지 모두 일치한다는 소리이다.

예) 만약 N =8이면, 임의의 두 수열은 [1,2,3,6,7,8,4,5] , [1,4,6,7,5,2,3,8] 이런 식으로 주어진다.

 

좀 더 간단한 예시를 위해 예제를 통해서 풀어보면 [1 3 2], [1 2 3] 의 LCS는 [1,2] or [1,3]이다.

• 이는 따지고보면 [1 2 3]은 index순대로 정렬이 되어있기 때문에 [1 3 2]의 가장 긴 증가하는 부분 수열(LIS)을 구하는 것과 다름없다. 
• 그래서 하나의 배열을 기준([1 2 3])으로 정하고 다른 배열([1 3 2])을 이 기준이 되는 배열과 비교하여 index를 정리하면 된다. 

따라서 하나의 배열을 기준 index로 정하고 다른 배열을 기준 index를 통해 다시 원소를 재배열한 다음 해당 배열의 LIS를 구하면 결국은 두 배열의 LCS를 찾는 것과 똑같다.

 

총 3가지의 자료구조를 사용하여 풀이를 한다.

• standard : 첫 번째로 주어진 배열로 비교의 기준이 되는 배열 
• arr : 두 번째로 주어진 배열의 값들의 index로 저장한 배열
• res : standard기준으로 arr 원소들의 상대적 위치를 저장하는 배열

설계

1. 처음으로 주어진 배열을 비교의 기준이 되는 배열standard로 지정 한다.
2. 그리고 두 번째로 주어진 배열 원소들이 저장된 Index를 arr배열에 저장한다.
3. standard를 기준으로 arr원소들이 상대적으로 어디에 저장되어 있는 위치를 새로운 배열 res에 저장한다.

예)

standard(기준) : [1 2 3] // 기준이 되는 배열

두 번째로 주어진 배열 : [1 3 2] // 두 번째 입력으로 주어진 배열

arr  : [0 2 1] // 1은 0번 index, 2는 1번 index, 3은 1번 인덱스에 위치해 있다.

  

res[i] = arr[standard[i]-1]+1;

   - res[0] = arr[standard[0]-1]+1 = arr[0]+1 = 1

   - res[1] = arr[standard[1]-1]]+1 = arr[2]+1 =3

   - res[2] = arr[standard[2]-1]]+1 = arr[1]+1 = 2

 

res : [1 3 2]

int[] standard = new int[n];
int[] arr = new int[n];
		
StringTokenizer st = new StringTokenizer(br.readLine());		
for(int i=0; i<n; i++) {
	standard[i] = Integer.parseInt(st.nextToken());
}
		
st = new StringTokenizer(br.readLine());
for(int i=0; i<n; i++) {
	int num =  Integer.parseInt(st.nextToken());
	arr[num-1] = i;
}
		
int[] res = new int[n];
for(int i=0; i<n ;i++) {
	res[i] = arr[standard[i]-1]+1;
}

예) standard 배열이 숫자가 아닌 하나의 기준이 된다는 것을 알아야한다.
standard(기준)  :  [1 4 6 7 5 2 3 8]
두 번째로 주어진 배열 : [1 2 3 6 7 8 4 5]
arr[num-1] = i
arr  :  [0 1 2 6 7 3 4 5]

res[i] = arr[standard[i]-1]+1;
res[0] = arr[standard[0]-1]+1 = arr[0]+1 = 1
res[1] = arr[standard[1]-1]+1 = arr[3]+1 = 7
res[2] = arr[standard[2]-1]+1 = arr[5]+1 = 4

...

res[7] =  arr[standard[7]-1]+1 = arr[7]+1 = 6

 

res : [ 1 7 4 5 8 2 3 6 ] 

만약 위의 과정이 헷갈린다면 기준이 되는 배열(standard)이 [a b c d e f g h]이라고 생각해보자.
두 번째로 주어진 배열은 [a d f g e b c h]이라고 하자.
그러면 res배열은 두 번째로 주어진 배열 그대로 [a d f g e b c h]이 된다.  

위의 두 번째로 주어진 배열 [1 2 3 6 7 8 4 5]도 알파벳 순이라고 가정하고 standard를 [ a b c d e f g h]로 바꿔서 생각하면 res배열은 그대로 [a d f g e b c h]가 된다.

하나의 배열을 기준으로 삼고 그거에 따른 새로운 수열을 하나 만드는 것이다.
그래서 이 힌트를 위해 예제를 보면 하나의 배열은 그냥 1~N 순차대로 주어진 것 같다. [1,2], [1,2,3]

 

이진탐색 LIS

위의 과정을 이해했으면 이제 남은 것은 res배열을 이진탐색을 통해 LIS길이를 구해주면 된다. res의 LIS(가장 긴 증가하는 부분 수열)을 구하면 그것이 standard와 arr의 최장 공통 부분 수열이 된다.

1. 처음으로 주어진 배열을 비교의 기준이 되는 배열(standard)로 지정한다.
2. 그리고 두 번째로 주어진 배열 원소들이 저장된 Index를 arr배열에 저장한다.
3. standard 배열을 기준으로 arr원소들이 상대적으로 어디에 저장되어 있는 위치를 새로운 배열 res에 저장한다.
4. 해당 res배열의 LIS를 이진탐색을 통해 구해준다

따라서, res 1 3 2 의 LIS → 1 2로 길이는 2이다.

 

풀이 코드 

// #13711 이진탐색 LCS4
import java.io.*;
import java.util.StringTokenizer;

public class Main {
	static int n;
	static int[] memo;
	public static void main(String[] args) throws IOException{
		BufferedReader br =new BufferedReader(new InputStreamReader(System.in));
		n = Integer.parseInt(br.readLine());
		int[] standard = new int[n];
		int[] arr = new int[n];
		
		StringTokenizer st = new StringTokenizer(br.readLine());		
		for(int i=0; i<n; i++) {
			standard[i] = Integer.parseInt(st.nextToken());
		}
		
		st = new StringTokenizer(br.readLine());
		for(int i=0; i<n; i++) {
			int num =  Integer.parseInt(st.nextToken());
			arr[num-1] = i;
		}
		
		int[] res = new int[n];
		for(int i=0; i<n ;i++) {
			res[i] = arr[standard[i]-1]+1;
		}
        
		// res의 LIS구하기 
		memo = new int[n+1];
		int answer = LIS(res);
		System.out.println(answer);
	}
	
	
	static int LIS(int[] arr) {
		int len=0;
		int idx=0;
		for(int i=0; i<n; i++) {
			if(arr[i] > memo[len]) {
				len +=1;
				memo[len] = arr[i];
			}else {
				idx = binarySearch(0, len, arr[i]);
				memo[idx] = arr[i];
			}
		}
		return len;
	}
	
	static int binarySearch(int left, int right, int key) {
		int mid =0;
		while(left<right) {
			mid = (left+right)/2;
			if(memo[mid] < key) {
				left = mid+1;
			}else {
				right = mid;
			}
		}
		return right;
	}
}