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

문제 링크

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

풀이 과정

최장 증가 부분 수열의 길이를 출력하는 문제입니다. 수열 크기 N의 최대 값이 100만이므로, 이중 for문 방식을 사용하면 시간 제한에 걸리게 됩니다. 따라서, $O(nlogn)$의 시간 복잡도를 갖는 이분 탐색의 방법을 사용해야 합니다.

이분 탐색을 이용한 LIS 알고리즘 구현은 [알고리즘 정리] 최장 증가 부분 수열(Longest Increasing Subsequence, LIS)에서 확인할 수 있습니다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main {
    static int[] arr;
    static int[] dp;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        arr = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        dp = new int[N];
        dp[0] = arr[0];
        int idx = 0;

        for (int i = 1; i < N; i++) {
            if (arr[i] > dp[idx]) {
                dp[++idx] = arr[i];
            } else {
                int targetIdx = binarySearch(idx, arr[i]);
                dp[targetIdx] = arr[i];
            }
        }

        System.out.println(idx + 1);
    }

    static int binarySearch(int high, int target) {
        int low = 0;

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

            if (dp[mid] < target) low = mid + 1;
            else high = mid - 1;
        }

        return low;
    }
}