[12015] 가장 긴 증가하는 부분 수열2

 

1. 문제설명

원소의 개수와 수열을 입력받는다.

이때 수열이

10 20 10 30 20 50 이라면,

가장 긴 증가하는 부분 수열은

10 20 30 50, 즉 LIS는 4가 된다.

 

2. 코드

import java.util.Scanner;

public class Fav_long_seq {
    public static int [] FLS;
    public static int newLength = 1;
    public static void main(String args[]){
        Scanner sc  = new Scanner(System.in);
        int N = sc.nextInt();
        int [] seq = new int[N];
        int [] newSeq = new int[N];

        for(int i=0;i<N;i++){
            seq[i] = sc.nextInt();
        }
        newSeq[0] = seq[0];

        //초기세팅

        for(int i = 0; i< seq.length; i++){

            if(newSeq[newLength - 1]< seq[i]){
                newLength++;
                newSeq[newLength -1] = seq[i];
            }
            else {
               binarySearch(newSeq, seq, i);
            }
//            for(int j=0;j<newSeq.length;j++){
//                System.out.print(newSeq[j]+", ");
//            }
//            System.out.println("\n");
        }
        System.out.println(newLength);
    }

    public static void binarySearch(int[] newSeq, int[] seq, int i){
        int low = 0;
        int high = newLength;

        while (low < high) {
            int mid = (low + high) / 2;

            if (newSeq[mid] < seq[i]) {
                low = mid + 1;
            } else {
                high = mid;
            }
        }
        newSeq[low] = seq[i];
    }
}

3. 풀이

예를들어 배열이

10 20 30 15 20 25 40 일때

For문의 i	대상 값	seq	newSeq	BinSearch value	newLength
1	10	10 20 30 15 20 25 40	10	x	1
2	20	10 20 30 15 20 25 40	10 20	x	2
3	30	10 20 30 15 20 25 40	10 20 30	x	3
4	15	10 20 30 15 20 25 40	10 15 30	20 -> 15	3
5	20	10 20 30 15 20 25 40	10 15 20	30 -> 20	3
6	25	10 20 30 15 20 25 40	10 15 20 25	x	4
7	40	10 20 30 15 20 25 40	10 15 20 25 40	x	5

위와 같이 진행된다.