[백준] 14002. 가장 긴 증가하는 부분 수열 4

문제 링크

[백준] 14002. 가장 긴 증가하는 부분 수열 4

풀이 과정

최장 길이 부분 수열의 길이와 수열을 이루는 요소들을 모두 출력하는 문제입니다. 이분 탐색의 방법과 역추적해서 수열을 이루는 요소들을 찾았습니다. [알고리즘 정리] 최장 증가 부분 수열(Longest Increasing Subsequence, LIS) 최장 증가 부분 수열]에서 확인할 수 있습니다.

코드

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

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

    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];
        tracking = new Pair[N];

        dp[0] = arr[0];
        tracking[0] = new Pair(0, arr[0]);
        int idx = 0;

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

        Deque<Integer> stack = new ArrayDeque<>();
        for (int i = N - 1; i >= 0; i--) {
            if (idx == tracking[i].first) {
                stack.push(tracking[i].second);
                idx--;
            }
        }

        StringBuilder answer = new StringBuilder(String.valueOf(stack.size()));
        answer.append("\n");
        
        while (!stack.isEmpty()) {
            answer.append(stack.pop());
            answer.append(" ");
        }

        System.out.println(answer);
    }

    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;
    }

    static class Pair {
        int first, second;

        public Pair(int first, int second) {
            this.first = first;
            this.second = second;
        }
    }
}