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

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

 

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

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

---

1.  아이디어

 

수열의 길이가 최대 100만 문제로 O(N^2)의 시간복잡도가 소요되는 기존의 다이나믹 프로그래밍 방식으로는 해결할 수 없는데 이분 탐색을 활용하면 O(N log N)으로 해결할 수 있다.

---

2. 문제풀이

 

Lower Bound 이분 탐색으로 수열을 돌며 해당 수가 dp 배열에 어디에 들어갈 수 있는지 찾는다. dp 배열은 인덱스가 LIS의 길이고 값에 해당 길이의 LIS의 마지막 원소가 들어간다. len은 현재까지 구한 LIS의 길이이다. 이분 탐색으로 얻은 인덱스로 dp 배열을 갱신해주고 만약 인덱스가 len 보다 크면 LIS의 길이가 1 늘어난 것이므로 len을 갱신해준다. 이분 탐색 과정에서 dp 배열의 패딩으로 left는 1, len이 아닌 len + 1을 right로 해서 LIS의 길이가 늘어나는 순간에 대한 탐색에 신경써줬다.

---

3. 코드

 

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

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

        int N = Integer.parseInt(br.readLine());

        int[] arr = new int[N];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        int[] dp = new int[1 + N];
        int len = 0;
        for (int i = 0; i < N; i++) {
            int idx = binarySearchLowerBound(dp, len, arr[i]);
            dp[idx] = arr[i];
            if (idx == len + 1) len++;
        }

        System.out.println(len);
    }

    private static int binarySearchLowerBound(int[] arr, int len, int target) {
        int left = 1;
        int right = len + 1;

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

            if (arr[mid] < target) left = mid + 1;
            else right = mid;
        }

        return right;
    }

}

---

4. 후기