LIS - Array List로 구하기

www.acmicpc.net/problem/12015

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

증가하는 부분수열을의 개수를 구하는 문제이다.

그동안 DP나 TreeSet.ceiling 을 이용해서 구했는데.. 

ArrayList를 이용해서 구하면 많이 바르다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.StringTokenizer;

public class BOJ_11053 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        int[] arr = new int[N];
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
        ArrayList<Integer> list = new ArrayList<>();
        list.add(0);
        for (int n: arr) {
            if(list.get(list.size()-1) < n) {
                list.add(n);
                continue;
            }

            int tmp = Collections.binarySearch(list, n);
            if (tmp > 0) list.set(tmp, n);
            else list.set(-tmp-1, n);
        }
        System.out.println(list.size()-1);
    }
}

 

여기서는 binarysearch를 Collections에서 제공하는 걸 사용했다.

 

Collections.binarysearch는

search 대상을 찾았을 때는 그 대상의 위치를,
만약 찾지 못했을때는 (- insertion point) - 1에 해당하는 값을 리턴하게 됩니다.

insertion point는 해당 리스트에 그 key가 존재 했다면, 그 key가 삽입되었을 위치를 말합니다.

List al = new ArrayList();         al.add(1);         al.add(2);         al.add(3);         al.add(10);         al.add(20);          // 10 은 현재 3번째 위치에 있습니다.         int index = Collections.binarySearch(al, 10);         System.out.println(index);          // 13 은 현재 없습니다. 13 은 4번째 위치에 추가 되었을 것 입니다.         // 그래서 이 함수는 (-4-1)         // 즉, -5를리턴하게 됩니다.

반드시 정렬 된 상태여야 합니다. 이진 탐색으로 값을 찾기 때문에 정렬이 되어 있지 않으면 이진 탐색을 할 수가 없습니다.