[Java] LIS (최장 증가 부분 수열) / binarySearch

Java BinarySearch 사용 방법

int insertIdx = Arrays.binarySearch(Arrays.copyOfRange(l, 0, lis+1), A[i]);
// Arrays.binarySearch 함수의 경우 원소 미발견되면 삽입 인덱스 위치 * (-1) - 1 값을 알려줌 
if (insertIdx < 0) {
	insertIdx = ( insertIdx + 1 ) * -1;
}

원소 key값 발견 시 원소 위치, 미발견 시 삽입 인덱스 위치 * (-1) - 1 값을 알려줌.
Arrays.binarySearch(배열, 키)

이때 배열은 정렬된 상태여야 함.

위 CASE 에서는 원소가 삽입되어 있는 마지막 위치까지만 서치하도록 배열의 부분만 복사함.

Java 배열 복사

Arrays.copyOfRange(배열, 시작인덱스, 끝지점);

이때 당연히 시작은 포함, 끝은 미포함 -> 수학 기호로 [시작, 끝) 이렇게.

이러한 배열 편의성 함수는 공식 문서 중 Arrays 에서 찾아볼 수 있도록 한다 (s 꼭 붙여야함)

LIS 전체 코드

입력으로 주어진 A 배열에서 LIS (가장 긴 증가 부분 수열) 의 길이를 찾아내는 코드이다.

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

public class Main {

    public static void main(String[] args) throws IOException {

        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(bf.readLine());
        
        int N = Integer.parseInt(st.nextToken());
        int[] A = new int[3001];

        StringTokenizer st2 = new StringTokenizer(bf.readLine());
        for (int i = 1 ; i <= N ; i++) {
            A[i] = Integer.parseInt(st2.nextToken());
        }
        A[0] = 0;

        // 동적계획법: LIS (Longest Increasing Subsequence)
        // logic from : https://namu.wiki/w/%EC%B5%9C%EC%9E%A5%20%EC%A6%9D%EA%B0%80%20%EB%B6%80%EB%B6%84%20%EC%88%98%EC%97%B4
        
        int[] D = new int[3001]; // A[i] 까지 이어지는 IS의 길이 
        D[0] = 1;

        int[] l = new int[3001]; // A[i] 보다 작은 수들 중 가장 큰 수의 값 
        l[0] = 1;

        int lis = 0; // 길이 
        for (int i = 0; i <= N; i++) {
            // D, l 배열은 길이를 따로 관리 : 그게 lis 값임. lis 갱신 시에만 갱신
            // A[i] 값과 l 배열을 비교하면서 (i 뒤로 가면서) l 배열에서 A[i] 보다 작은 값을 찾는다.
            // 이때 l 배열은 항상 오름차순 정렬되어 있으므로 full search 할 필요가 없고 binary search 가능
            // 그래서 full search 했으면 O(n**2) 인데 binary search 해서 O(nlogn)

            int insertIdx = Arrays.binarySearch(Arrays.copyOfRange(l, 0, lis+1), A[i]);
            // Arrays.binarySearch 함수의 경우 원소 미발견되면 삽입 인덱스 위치 * (-1) - 1 값을 알려줌 
            if (insertIdx < 0) {
                insertIdx = ( insertIdx + 1 ) * -1;
            }

            // System.out.println("i: " + i + " A[i]: " + A[i]  + " insertIdx: " + insertIdx + " lis: " + lis);
            
            if (insertIdx <= lis) {
                // LIS 갱신 안 됨
                if (A[i] < l[insertIdx]) {
                    l[insertIdx] = A[i];
                }
            } else {
                // LIS 갱신 
                //System.out.println("lis 갱신");
                lis = lis+1;
                D[lis] = D[lis-1] + 1; // 길이 갱신
                l[lis] = A[i];
            }
        }

        /* 
        System.out.println("---A---");
        for (int i = 0; i<=N; i++) {
            System.out.print(A[i] + " ");
        }
        System.out.println(" ");

        System.out.println("---D---");
        for (int i = 0; i<=N; i++) {
            System.out.print(D[i] + " ");
        }
        System.out.println(" ");

        System.out.println("---l---");
        for (int i = 0; i<=N; i++) {
            System.out.print(l[i] + " ");
        }
        System.out.println(" "); 
        */

        
        // answer : lis 길이
        System.out.println(lis);

        return;
    }
}