백준 12015번 가장 긴 증가하는 부분 수열2 (JAVA)

https://www.acmicpc.net/problem/12015

12015번: 가장 긴 증가하는 부분 수열 2

 

전형적인 LIS 문제입니다. 하지만 N의 크기가 1,000,000 이기 때문에 이중for문으로 작성하면 시간초과가 날 것이라 생각합니다. 저는 DP 배열을 만들어binary search를 통해 해당 원소가 DP배열에 어디에 들어가야하는지 판단하여 위치가 DP에 들어있는 원소보다 크다면 size를 하나 늘려 최장 증가 수열의 길이를 찾았습니다. 

 

 

package BOJ;

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

public class BOJ_12015 {

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        int n = Integer.parseInt(st.nextToken());
        int[] input = new int[n];
        int[] LIS = new int[n];
        st = new StringTokenizer(br.readLine()," ");
        for(int i = 0; i < n ; i++){
            input[i] = Integer.parseInt(st.nextToken());
        }
        int size = 0;
        for(int i = 0 ; i < n ; i++){
            int temp = Arrays.binarySearch(LIS,0,size,input[i]);
            if(temp < 0){
                temp = Math.abs(temp) - 1;
                LIS[temp] = input[i];
                if(size == temp) size++;
            }
        }
        System.out.println(size);
    }
}