[14003] 가장 긴 증가하는 부분 수열 5

문제 링크 : https://www.acmicpc.net/problem/14003

14003번: 가장 긴 증가하는 부분 수열 5

 

문제 해결 방법

14002번과 같은 문제이지만 입력 크기가 훨씬 커서 이진 탐색을 이용한 LIS를 구현했다.

 

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int N = sc.nextInt();
        int[] arr = new int[N];
        int[] length = new int[N];
        ArrayList<Integer> list = new ArrayList<>();
        list.add(Integer.MIN_VALUE);

        for (int i = 0; i < N; i++) {
            arr[i] = sc.nextInt();
        }

        for (int i = 0; i < N; i++) {
            int num = arr[i];
            if (num > list.get(list.size() - 1)) {
                list.add(num);
                length[i] = list.size() - 1;
            } else {
                int left = 0;
                int right = list.size() - 1;

                while (left < right) {
                    int mid = (left + right) / 2;
                    if (list.get(mid) >= num) {
                        right = mid;
                    } else {
                        left = mid + 1;
                    }
                }
                list.set(right, num);
                length[i] = right;
            }
        }

        int idx = list.size() - 1;
        Deque<Integer> q = new LinkedList<>();
        for (int i = N - 1; i >= 0; i--) {
            if (idx == length[i]) {
                q.push(arr[i]);
                idx--;
            }
        }

        System.out.println((list.size() - 1));
        while (!q.isEmpty()) {
            System.out.print(q.pop() + " ");
        }
    }

}