[BOJ 12015] 가장 긴 증가하는 수열2 - JAVA, Gold2

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

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

사용한 알고리즘 : LIS(Longest Increasing Subsequence), 이분 탐색

 

풀이전략

LIS를 구하기 위한 전략은 아래와 같다.

위 그림처럼 입력받은 수가 수열의 최우측 원소와 비교했을 때 더 작다면

기존에 입력된 수열에서 같거나 더 크지만 가장 작은 수와 교체한다.

 

만약 입력받은 수가 수열의 최우측 원소보다 크다면, length의 길이를 1 늘리고

수열 최우측 바로 옆 인덱스에 값을 삽입한다.

 

위 과정을 반복하면 수열 내부의 원소는 변할지라도,

우리가 구하고자 하는 가장 긴 증가하는 수열의 크기를 알 수 있다.

 

단, 주의할 점이 하나 있다.

만약 입력받은 수를 기존 입력된 수와 비교하는 과정을 Brute Force 방식으로 진행한다면

시간 복잡도는 O(N^2)이 된다.

 

그런데 수열 A는 최대 1,000,000까지 가능하므로 최악의 경우 1,000,000,000,000(1조)번의 연산이 수행된다.

(실제로는 더 적지만 단순 시간 복잡도에 대입해 보았을 경우)

 

JAVA는 초당 1억 번의 연산이 가능한데, 이는 1만초가 필요하단 뜻으로 시간초과가 발생한다.

 

따라서 기존 수열과 비교하는 과정을 이분 탐색을 이용해야한다.

이분 탐색의 경우 시간 복잡도가 O(NlogN)으로

최악의 경우 1,000,000 * log2(1,000,000) = 1,000,000 * 19.931569 = 19,931,569(약 2000만)번의

연산이 수행되고 0.2초면 계산이 완료된다.

 

 

제출코드

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

public class Main{
    static int subSet[];

    static int binarySearch(int start,int end,int val){
        while(start<end){
            int mid = (start+end)/2;

            if(val==subSet[mid]){
                return mid;
            }
            else if(val>subSet[mid]){
                start=mid+1;
            }
            else{
                end=mid-1;
            }
        }

        if(val>subSet[start]) return start+1;
        else return start;
    }

    public static void main(String args[]) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        int N = Integer.parseInt(br.readLine());

        subSet = new int[N];
        int ans=0;

        st = new StringTokenizer(br.readLine());

        subSet[0]=Integer.parseInt(st.nextToken());
        ++ans;
        while(st.hasMoreTokens()){
            int inputNum=Integer.parseInt(st.nextToken());
            if(subSet[ans-1]>=inputNum){
                int diffIndex=binarySearch(0,ans-1,inputNum);
                subSet[diffIndex]=inputNum;
            }
            else subSet[ans++]=inputNum;
        }

        bw.write(ans+"\n");
        bw.flush();
        bw.close();
    }
}