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

문제 원본 : https://www.acmicpc.net/problem/14003

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

import java.io.*;
import java.util.ArrayList;
import java.util.Collections;
import java.util.StringTokenizer;

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

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

        int[] arr = new int[n];
        int[] arr2 = new int[n];
        int[] dp = new int[n];

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

        int arr2Size = 0;
        for (int i = 0; i < n; ++i) {
            if (arr2Size == 0 || arr2[arr2Size - 1] < arr[i]) {
                arr2[arr2Size++] = arr[i];
                dp[i] = arr2Size;
            } else {
                int idx = binarySearch(arr2, 0, arr2Size - 1, arr[i]);
                if (arr2[idx] > arr[i]) {
                    arr2[idx] = arr[i];
                }
                dp[i] = idx + 1;
            }
        }

        ArrayList<Integer> ans = new ArrayList<>();
        StringBuilder builder = new StringBuilder();
        int val = arr2Size;
        for (int i = n - 1; i >= 0; --i) {
            if (dp[i] == val) {
                ans.add(arr[i]);
                --val;
            }

            if (val == 0) {
                break;
            }
        }
        Collections.reverse(ans);

        bw.write(String.valueOf(arr2Size));
        bw.newLine();

        for (Integer i : ans) {
            builder.append(i).append(" ");
        }
        bw.write(builder.toString());

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

    public static int binarySearch(int[] arr, int start, int end, int target) {
        int mid = 0;
        while (start <= end) {
            mid = (start + end) / 2;

            if (arr[mid] == target) {
                return mid;
            } else if (arr[mid] < target) {
                start = mid + 1;
            } else {
                end = mid - 1;
            }
        }

        return start;
    }
}

• LIS 알고리즘의 O(nlgn) 방식이다
• 상세 알고리즘은 나무위키를 참조하자.
• 이 문제를 풀면 11053, 12015, 12738, 14002 문제는 전부 하위 호환이기 때문에 사실상 다 푼 거나 다름없다.
• 입출력이 100만 개를 넘어가서 Scanner를 써서 제출했더니 시간 초과가 났다.
• BufferedReader, BufferedWriter 사용을 습관화해야겠다.
• 실제로 12015 문제를 BufferedReader, BufferedWriter를 써서 제출하니 Scanner를 써서 제출한 것에 비해 3배 이상 빨라진 것을 확인할 수 있었다.