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

#12738 가장 긴 증가하는 부분 수열3

난이도 : 골드 2

유형 : 이진탐색/ LIS

12738번: 가장 긴 증가하는 부분 수열 3

▸ 문제

수열 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의 가장 긴 증가하는 부분 수열의 길이를 출력한다.

 

문제 풀이  

백준 12015번 가장 긴 증가하는 부분 수열2와 문제가 중복된다. 다만 수열 A의 원소 Ai의 범위만 다르다. 해당 문제의 원소 범위는 음수까지 포함이다.

• DP를 통해 풀이를 하면 시간초과가 발생한다. O(n^2)
• 이진탐색을 통한 LIS 구하는 방법이 있으므로 해당 방식을 사용해야 한다. O(nlogn)

 

0~n-1개의 원소를 순차적으로 탐색하면서 LIS길이가 len인 부분 수열의 마지막 값중 최솟값을 memo[len]에 저장해준다.

• memo[len] = LIS길이가 len인 부분 수열 마지막 원소 중 최솟값
  • {10, 20, 10, 30, 20, 50} len = 1, memo[len] =  10

여기서 만약 마지막 원소 최솟값이 더 작은 값이 나오면 memo배열을 update시켜줘야 하는데, 선형탐색을 하면 O(n)이 되므로 이진탐색을 통해 memo배열의 index를 O(logn) 시간복잡도로 구해준다.

 

설계

해당 문제 원소의 최솟값은 음수이므로, 처음 memo[0] 값을 비교할 때 초기값을 (해당 원소의 최솟값-1)로 설정해준다. memo[0] = -1,000,000,001

1. 다음에 올 숫자(arr[i])가 현재 마지막 값 중 최솟값(memo[len])이랑 비교한다. 
   1. if(arr[i] > memo[len]) LIS 조건이 성립하므로 값을 넣어주고 len을 1 늘려준다. memo[len+1] = num
2. 1번에 해당되지 않을 경우, 다음에 올 숫자(arr[i])가 수열의 최솟값과 최댓값 사이의 값이므로 이진탐색을 통해 삽입할 idx를 찾는다.
   1. 현재 memo={1,2,7}이고 arr[i] = 3이면, 이는 1,2,7보다는 뒤에 등장하는 수이고 또 1,2보다 크기보다는 크고 7보다는 작은 값이다.
      1. 그러므로 이진탐색을 통해 memo[i-1] < num <= memo[i]인 곳을 찾아 memo[i] = num을 갱신해준다.
3. 최종적으로 탐색을 진행하면서 num에 따라 해당 조건을 넣어주면 된다.

 

풀이 코드

import java.io.*;
import java.util.StringTokenizer;

public class Main{
	static int[] memo;
	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());
		}
		
		memo = new int[n+1];
		memo[0] = -1_000_000_001;
		int len=0, idx=0;
		for(int i=0; i<n; i++) {
			if(arr[i] > memo[len]) {
				memo[++len] = arr[i];
			}else {
				idx = binarySearch(0, len, arr[i]);
				memo[idx] = arr[i];
			}
		}
		System.out.println(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;
	}
}