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

https://www.acmicpc.net/problem/14003

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

 

 

문제 접근법은 이전에 푼 문제들과 동일하지만

부분 수열을 출력해야한다

A의 요소마다 인덱스값을 저장하는 배열을 만들고

뒤에서부터 값을 하나씩 줄여가면서 size 크기의 배열을 만든다

앞에서부터 만들면 다음 값이 작아지는 구간에 대처하기가 힘들다

뒤에서부터 접근하면 size가 8일때 최초로 등장하는 8미만의 수를 배열에 담아서 출력하면 된다

 

import java.io.*;
import java.util.*;

public class Main {
    static final int MAX_N = 1000000;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int[] arr = Arrays.stream(br.readLine().split(" "))
                .mapToInt(Integer::parseInt).toArray();
        int[] D = new int[MAX_N];
        D[0] = arr[0];
        int[] result = new int[arr.length];
        result[0] = 0;
        int size = 1;
        for (int i = 1; i < N; i++) {
            int index = Arrays.binarySearch(D, 0, size, arr[i]);

            index = index >= 0 ? index : Math.abs(index) - 1;
            D[index] = arr[i];
            if (index == size) {
                size++;
            }
            result[i] = index;
        }
        String[] str = new String[size];
        System.out.println(size);
        size--;
        for(int j = arr.length-1; j >= 0; j--) {
            if (size == -1) break;
            if (result[j] == size) {
                str[size] = String.valueOf(arr[j]);
                size--;
            }
        }
        System.out.println(String.join(" ", str));
    }
}

 

배열을 만들때 StringBuilder로 앞에서부터 붙였더니 시간초과로 실패했다