[BOJ] 백준 14003번 가장 긴 증가하는 부분 수열 5 LIS - 이진탐색 (Java)

#14003 가장 긴 증가하는 부분 수열5

난이도 : 플레 5 

유형 : 이진 탐색 / LIS / DP

14003번: 가장 긴 증가하는 부분 수열 5

▸ 문제

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.

예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.

▸ 입력

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

둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (-1,000,000,000 ≤ Ai ≤ 1,000,000,000)

▸ 출력

첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다.

둘째 줄에는 정답이 될 수 있는 가장 긴 증가하는 부분 수열을 출력한다.

 

문제 풀이  

백준 12738번 가장 긴 증가하는 부분 수열3의 확장 문제이다. 주어진 수열의 크기가 작을 경우(1000이하) DP만 사용하여 이중포문으로 해결해도 되지만 해당 문제와 같이 수열의 크기가 100만 정도로 크게 주어진 경우는 더 효율적인 방식을 사용해야 한다.

 

LIS는 이진탐색으로도 구할 수 있다. (참고) 이진 탐색을 활용하면 O(n^2)에서 O(nlogn)으로 줄일 수 있게된다.

 

구상

이진탐색을 통해 구할 수 있는 데이터

lis[]는 1차원배열로 길이(len)에 따른 LIS 수열 원소 값을 저장한다.

• lis[len] =0~i의 arr의 원소배열 중 LIS의 길이가 len인 부분수열들의 마지막값 중 최솟값

arr[i]	1	5	6	2	3	4
lis[i]	1	2	3	4	-	-

 

해당 방식은 주어진 수열 데이터를 순차적으로 비교해가며 이진탐색을 통해 적절한 위치에 삽입을 해주는 방식이다. 그래서 바로 lis배열에 저장된 데이터를 출력하면 될 것 같지만 아니다. 반례는 다음과 같다.

• 마지막 원소 5는 10보다 작으므로 맨 앞자리에 갱신되어 들어가게 된다. 

arr[i]	10	20	30	5
lis[i]	5	20	30	0

 

증가 부분 수열 크기를 담는 데이터 추가

그러므로 dp[] 1차원 배열을 하나 더 추가하여 데이터를 하나 더 수집할 것이다. 해당 배열에는 인덱스에 따른 증가 부분 수열의 크기를 저장해준다.

• dp[i] = arr[i]의 증가 부분 수열 크기 

arr[i]	10	20	30	5
lis[i]	5	20	30	-
dp[i]	1	2	3	1

 

설계

1. LIS를 구하는 과정은 LIS 이진탐색 풀이와 동일하다.
2. 해당 과정에 부분 수열 크기(len)을 dp에 저장하는 부분만 추가해준다.
   1. if(arr[i] > lis[len]),  dp[i] = ++len;
   2. else, dp[i] = idx
3. Stack 자료구조와 LIS 크기, dp의 데이터를 가지고 역추적으로 LIS 수열을 탐색한다.  if(dp[i] == len) s.push(arr[i])
4. Stack에 저장된 데이터를 출력해준다.

 

시뮬레이션

arr[i]	10	20	30	5
lis[i]	5	20	30	-
dp[i]	1	2	3	1

LIS 길이 (len) : 3

• dp를 i: n-1 ~ 0으로 역순으로 탐색한다.
  • dp[3] != 3
  • dp[2] == 3, s.push(arr[2])
  • dp[1] == 2, s.push(arr[1])
  • dp[0] == 1, s.push(arr[0])

 

풀이 코드 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;
import java.util.StringTokenizer;

public class Main {
	static int[] lis;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
	
		int[] arr = new int[n];
		StringTokenizer st = new StringTokenizer(br.readLine());
		for(int i=0; i<n; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}
		
		lis = new int[n+1];  // 0~i의 arr의 원소배열 중 LIS의 길이가 len인 부분수열들의 마지막 값 중 최솟값
		lis[0] = -1_000_000_001;
		int[] dp = new int[n]; // 증가 부분 수열 크기 저장   
		int len =0;
		int idx =0;
		for(int i=0; i<n; i++) {
			if(arr[i] > lis[len]) {
				dp[i] = ++len;
				lis[len] =arr[i];
				
			}else {
				idx = binarySearch(0, len, arr[i]);
				lis[idx] = arr[i];
				dp[i] = idx;
			}
		}
		
		StringBuilder sb = new StringBuilder();
		sb.append(len+"\n");
		
		Stack<Integer> s = new Stack<>();
		for(int i=n-1; i>=0; i--) {
			if(dp[i] == len) {
				s.push(arr[i]);
				len--;
			}
		}
		
		while(!s.isEmpty()) {
			sb.append(s.pop()+" ");
		}
		System.out.println(sb.toString());
        
	}
    
	static int binarySearch(int left, int right, int key) {
		int mid =0;
		while(left < right) {
			mid = (left+right)/2;
			
			if(lis[mid] < key) {
				left = mid+1;
			}else {
				right = mid;
			}
		}
		return right;
	}
}