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

문제 링크

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

풀이 과정

[백준] 14002. 가장 긴 증가하는 부분 수열 4와 N과 수열을 이루는 요소의 범위만 다르고 같습니다. 최장 증가 부분 수열의 길이와, 수열을 이루는 모든 요소들을 같이 출력하는 문제입니다.

[백준] 14002. 가장 긴 증가하는 부분 수열 4와 동일한 코드를 제출해서 맞았습니다.

코드

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