가장 긴 증가하는 수열 ( 백준 12015 )

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

 

* 입력값이 증가

* 이분탐색을 이용해서 증가하는 수열의 길이를 찾는 문제

* 보통 이분탐색 ( 매개변수 탐색 x ) 이라고 하면 정렬된 배열에서 값을 찾는 알고리즘이다

* 입력값으 정렬은 되어 있지 않으니까 사용이 불가능

* 따라서 입력값의 배열의 요소를 한개씩 탐색하며 이분탐색을 넓혀가야한다

* 아래는 그 예시이다

 

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

class BOJ12015 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int size = Integer.parseInt(br.readLine()), length = 0;
        int[] arr = new int[size], lis = new int[size];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i = 0; i < size; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
        for(int target : arr) {
            int pos = binarySearch(lis, length, target);
            lis[pos] = target;
            if(pos == length) length++;
        }
        System.out.println(length);
    }
    private static int binarySearch(int[] lis, int length, int target) {
        int left = 0, right = length;
        while(left < right) {
            int mid = (left+right)/2;
            if(lis[mid] >= target) {
                right = mid;
            }
            else {
                left = mid + 1;
            }
        }
        return left;
    }
}

* 새로운 위치는 lis 배열에 갱신하고

* 이미 존재하는 값은 lower bound 탐색을 통해 값을 덮어써준다

* 따라서 lower bound 코드를 작성해주면되는데

* 조건을 target을 기준으로 같거나 작게 설정하면 된다