[Algo] 백준 12015 가장 긴 증가하는 부분 수열 5 JAVA

문제 바로가기 : https://www.acmicpc.net/problem/14003

메모리 : 307804KB

시간 : 944ms

언어 : Java 11

---

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;
import java.util.StringTokenizer;

public class Main {
    static int[] arr, vector;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        int N = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        arr = new int[N]; // 맨 처음 수열
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        // 최장수열만들기
        vector = new int[N]; // 최장부분수열
        int end = 0; // 벡터에서 맨 마지막 인덱스
        int[] idx = new int[N]; // arr[i]가 vector의 어느자리에 들어가는지
        vector[0] = arr[0];
        idx[0] = 0;
        for (int i = 1; i < N; i++) {
            if (vector[end] < arr[i]) { // 벡터마지막 값보다 수열의 값이 크면 벡터에 저장
                vector[++end] = arr[i];
                idx[i] = end;
            } else { // 값이 작으면 적절한 위치 탐색
                int reidx = replace(arr[i], 0, end);
                vector[reidx] = arr[i];
                idx[i] = reidx;
            }
        }

        // 출력
        Stack<Integer> stack = new Stack<>();
        int b = end;
        for (int i = N - 1; i >= 0; i--) {
            if (idx[i] == b) { // idx가 출력순서와 맞으면 저장
                stack.add(arr[i]);
                b--;
            }
        }
        sb.append(end + 1 + "\n");
        while (!stack.isEmpty()) {
            sb.append(stack.pop() + " ");
        }
        System.out.println(sb);
    }

    /** 적절한 자리를 찾아서 숫자를 교체한다 */
    private static int replace(int num, int left, int right) {
        while (left < right) {
            int mid = (left + right) / 2;
            if (vector[mid] < num) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return right;
    }
}