[알고리즘] Java / 백준 / 가장 긴 증가하는 부분 수열 3 / 12738

[알고리즘] Java / 백준 / 가장 긴 증가하는 부분 수열 3 / 12738

문제

문제 링크

접근 방식

수열의 크기가 1,000,000 이므로 dp로 풀면 O(n^2) 이기 때문에 시간 초과가 난다.

따라서 이분 탐색으로 풀어야 한다.

코드

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

public class Main_12738 {

	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		int nums[] = new int[N];
		for(int i=0;i<N;i++) {
			nums[i] = Integer.parseInt(st.nextToken());
		}
		
		// 이분탐색을 이용한 LIS
		// 필요한 것 
		// 1. LIS 배열
		// 2. LIS size
		
		int[] LIS = new int[N];
		int size = 0;
		
		for(int i=0;i<N;i++) {
			int temp = Arrays.binarySearch(LIS, 0, size, nums[i]);
			if(temp < 0) temp = Math.abs(temp) - 1; // 들어가야 할 위치를 뜻함
			
			LIS[temp] = nums[i];
			
			if(temp == size) {
				size++;
			}
		}
		
		System.out.println(size);
	}
}