[백준/이분탐색] 12015번 가장 긴 증가하는 부분 수열 2 (JAVA)

문제

---

풀이

가장 긴 증가하는 부분 수열 1 문제는 n의 범위가 작아서 DP로 풀 수 있었지만, 이번 문제는 n의 범위가 100만까지 늘어났기 때문에 DP로는 풀 수 없다. 따라서 이분 탐색으로 문제에 접근해야 한다.

전체적인 풀이는, List의 적절한 위치에 원소들을 삽입해가는 방식으로 이루어진다. 주어진 arr의 원소들을 한 번씩 탐색하고, 각 원소마다 List에서 적절한 위치를 이분 탐색으로 찾는 것으로, 총 O(NlogN)의 시간복잡도로 해결 가능하다.

또한, LIS 전체를 구하는 것이 아니라 길이만 구하면 되기 때문에 하나의 List만 활용해서 O(N)의 공간복잡도로 문제 해결이 가능하다.

원소 arr[i]를 삽입하는 방법은 두 가지 경우로 나뉘어진다.

1. lis의 마지막 원소보다 큰 경우: lis의 마지막에 add()
2. lis의 마지막 원소 이하인 경우: lis에서 arr[i] 이상 값 중 최솟값의 index를 찾아서 set(index, arr[i])

코드

import java.io.*;
import java.util.ArrayList;
import java.util.List;

public class Main {

    private static int n;
    private static int[] arr;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        parseInput(br);
        int answer = findLISLength();
        bw.append(String.valueOf(answer));

        br.close();
        bw.close();
    }

    private static void parseInput(BufferedReader br) throws IOException {
        n = Integer.parseInt(br.readLine());
        arr = new int[n];
        String[] line = br.readLine().split(" ");
        for (int i = 0; i < n; i++) arr[i] = Integer.parseInt(line[i]);
    }

    private static int findLISLength() {
        List<Integer> lis = new ArrayList<>();
        lis.add(0);
        for (int i = 0; i < n; i++)
            if (arr[i] > lis.get(lis.size() - 1)) lis.add(arr[i]);
            else lis.set(findIndex(lis, arr[i]), arr[i]);
        return lis.size() - 1;
    }

    private static int findIndex(List<Integer> lis, int current) {
        int left = 0, right = lis.size() - 1, mid;
        while (left < right) {
            mid = (left + right) / 2;
            if (current > lis.get(mid)) left = mid + 1;
            else right = mid;
        }
        return (left + right) / 2;
    }
}

---

참고

[백준 11053 / 백준 12015] 가장 긴 증가하는 부분 수열(LIS: Longest Increasing Subsequence) - 1
[백준 12015 : JAVA] 가장 긴 증가하는 부분 수열 2 / 이진탐색 풀이