[백준 12015번] LIS(최장 증가 부분 수열) 이분탐색

문제 링크: 12015번 가장 긴 증가하는 부분 수열 2

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

 

먼저 lower bound에 대해 알아야 한다. lower bound는 처음으로 나온 key보다 큰 수의 위치를 말한다. 이는 이분탐색 과정을 조금만 응용하면 된다.

 

static int lowerBound(ArrayList<Integer> list, int target) {
    int left = 0;
    int right = list.size();
    int mid;

    while (left <= right) {
        mid = (left+right) / 2;

        if (list.get(mid) >= target)
            right = mid-1;
        else
            left = mid+1;
    }

    return left;
}

 

배열이 아닌 리스트로 구현해 두어서 좀 보기 불편하긴 하지만... 언젠가 left > right이 성립할 때, left는 lower bound를 가리키고 있다. arr[mid] == key일 때 mid+1을 바로 반환하지 않는 것은 중복되는 원소가 있을 수 있기 때문이다.

 

한편 i는 배열 전체를 순회하는데, 만약 arr[i]가 list의 가장 마지막 숫자 즉 가장 큰 숫자보다 크다면 이는 arr[i]가 list의 마지막에 붙을 수 있음을 의미한다.

그렇지 않다면? 그렇다고 해서 arr[i]를 그냥 넘어가는 것이 아니라... list가 LIS를 만족하면서도 후에 다른 숫자가 들어올 수 있도록 arr[lower_bound]를 갱신된 값으로 바꾸어준다.

물론 이렇게 하면 list 자체가 LIS와 동일한 것은 아니지만, 길이는 (가장 처음에 추가한 0만 제외한다면) LIS와 동일한 것이다.

 

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

public class Main {
    static int lowerBound(ArrayList<Integer> list, int target) {
        int left = 0;
        int right = list.size();
        int mid;

        while (left <= right) {
            mid = (left+right) / 2;

            if (list.get(mid) >= target)
                right = mid-1;
            else
                left = mid+1;
        }

        return left;
    }

    static int last(ArrayList<Integer> list) {
        return list.get(list.size() - 1);
    }

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

        st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());

        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 i = 0; i < n; i++) {
            if (arr[i] > last(list)) {
                list.add(arr[i]);
                continue;
            } else if (arr[i] < last(list)) {
                int idx = lowerBound(list, arr[i]);
                list.set(idx, arr[i]);
            }
        }

        System.out.print(list.size() - 1);
    }
}