<Algorithm> 82. 3745번 오름세

1. 3745번 오름세

• 배열이 주어지면 그 배열의 증가하는 부분 수열의 길이를 구하는 문제

• O(N^2)에 경우는 쉽게 이해했지만 N log(N) 푸는것은 쉽지 않았다.

• 이 알고리즘은 LIS(Longest increasing subsequence) 이다.

• 주어진 input 값이 

import java.io.IOException;
import java.util.Arrays;
import java.util.Scanner;
 
public class Main {
    static int N, Answer;
    static int [] arr;
    static int [] order;
    
    public static void main(String[] args) throws IOException {
        // TODO Auto-generated method stub
        
        Scanner sc = new Scanner(System.in);
        
        while(sc.hasNext()){
            N = sc.nextInt();
            arr = new int [N];
            order = new int[N];
            Arrays.fill(order, 1);
            
            for(int i=0; i<N; i++){
                arr[i] = sc.nextInt();
            }
            /*
            for(int i = 1 ; i < N; i++) {
                for(int j = 0; j < i; j++) {
                    if(arr[i] > arr[j] && order[j]+1 > order[i]) {
                        order[i] = order[j] + 1;
                    }
                }
            }
*/            /*Arrays.sort(order);
            System.out.println(order[N-1]);*/
            
            
            int T[] = new int[N];
            int T_val[] = new int[N];
            int R[] = new int[N];
            
            Arrays.fill(R, -1);
            
            T_val[0] = arr[0];
            int len = 0;
            
            for(int i = 1; i < N ; i++) {
                /*System.out.println("들어온다 : " + arr[i]);
                System.out.println("현재 T_val "+Arrays.toString(T_val));
                System.out.println("len : "+ len);
                System.out.println();
                */if(T_val[len] < arr[i]) {
                    //System.out.println("붙인다 : tval = " +T_val[len]+" arr = "+arr[i]);
                    T[len] = i;
                    len++;
                    T_val[len] = arr[i]; 
                    /*System.out.println("T_val 추가 ~ "+Arrays.toString(T_val));
                    System.out.println("len : "+ len);
                    System.out.println();*/
                }else {
                    int index =lowerBound(T_val, arr[i], 0, len);
                    T_val[index] = arr[i];
                    T[index] = i;
                    /*System.out.println("len : "+ len);
                    System.out.println("추출 index : "+index);
                    System.out.println("T_val 변화 ~ "+Arrays.toString(T_val));
                    System.out.println();*/
                }
            }
            
            /*System.out.println(Arrays.toString(T_val));
        */    System.out.println(len+1);
        }
        
    }
    public static int lowerBound(int[] array, int key, int start, int end) {
        if(start >= end) {
            if(start - 1 != -1)
                return start;
            else
                return 0;
        }
        
        // 4 7 10
        // end = 2
        // start = 0
        // mid = 1;
        // key 10;
        //  10 < 7  false
        // start = 2 end = 2
        int mid = (start+end)/2;
        
        if(key <= array[mid]) {
            return lowerBound(array, key, start, mid);
        }else {
            return lowerBound(array, key, mid+1, end);
        }
        
        
    }
}
    
    /*public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        
        while(true) {
            String str = br.readLine();
            if(str.equals("")) {break;}
            int N = Integer.parseInt(str);
            int arr[] = new int[N];
            int order[] = new int[N];
            Arrays.fill(order, 1);
            StringTokenizer st = new StringTokenizer(br.readLine());
            
            for(int i = 0; i < N; i++) {
                arr[i] = Integer.parseInt(st.nextToken());
            }
            
            for(int i = 1 ; i < N; i++) {
                for(int j = 0; j < i; j++) {
                    if(arr[i] > arr[j] && order[j]+1 > order[i]) {
                        order[i] = order[j] + 1;
                    }
                }
            }
            Arrays.sort(order);
            System.out.println(order[N-1]);
        }
}
    }*/
 

참고 & 출처  http://stack07142.tistory.com/56