백준 14003 자바 - 가장 긴 증가하는 부분 수열 5 문제

앞서 풀었던 가장 긴 증가하는 부분 수열 2번에 수열 index를 같이 셋팅한 뒤 계산한다고 보면 된다. 

 

가장 긴 증가하는 부분 수열 2번에 수열에서는 

i               0 1 2 3 4 5
arr            1 5 6 2 3 4
listForSize   0 1 2 3 

이렇게 까지만 구한뒤 listForSize의 값을 이용해서 길이를 구했다. 여기에

자신 증가하는 수열의 몇번째를 차지하고 있는지에 대한 리스트를 추가한다. 위에 예에 추가하면 아래와 같다.

i               0 1 2 3 4 5
arr            1 5 6 2 3 4
listForSize   0 1 2 3

indexs       0 1 2 1 2 3 

 

이부분에서 입력받은 수열 arr(A)를 뒤에서 부터 순회하면서 값을 체크한다.

int index = listForSize.size() - 1;
Stack<Integer> stack = new Stack<>();
    for(int i = N-1; i >= 0; i--) {
    	if(indexs[i] == index) {
    	index--;
    	stack.push(arr[i]);
    }
}		

순회를 돌면 아래와 같다.

index = 3

 - i = 5, indexs[5] = 3 -> arr[5] = 4 -> stack = {4}

 

index = 2

 - i = 4, indexs[4] = 2 -> arr[4] = 3 -> stack = {3, 4}

 

index = 1

 - i = 3, indexs[3] = 1 -> arr[3] = 2 -> stack = {1, 2, 3}   

 

 

 

index = 0

 - i = 2, indexs[2] = 2 -> x

 - i = 1, indexs[1] = 1 -> x

 - i = 0, indexs[0] = 0 -> arr[0] = 1 -> stack = {0, 1, 2, 3} 

 

이후 stack의 값을 꺼내주면 된다.

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

// 가장 긴 증가하는 부분 수열 5 문제 - 14003번
public class Main{

    static int N;

    public static void main(String[] args)throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        ArrayList<Integer> listForSize = new ArrayList<>();
        listForSize.add(Integer.MIN_VALUE);

        N = Integer.parseInt(br.readLine());
        int[] arr = new int[N];
        int[] indexs = new int[N];

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

        for(int i = 0; i < N; i++) {
            if(listForSize.get(listForSize.size()-1) < arr[i]) {
                listForSize.add(arr[i]);
                indexs[i] = listForSize.size() - 1;
            }
            else {
                int left = 1;
                int right = listForSize.size()-1;

                while (left < right) {
                    int mid = (left + right) / 2;
                    if(listForSize.get(mid) < arr[i]) {
                        left = mid + 1;
                    }else {
                        right = mid;
                    }
                }
                listForSize.set(right, arr[i]);
                indexs[i] = right;
            }
        }
        System.out.println(listForSize.size() - 1);

        int index = listForSize.size() - 1;
        Stack<Integer> stack = new Stack<>();
        for(int i = N-1; i >= 0; i--) {
            if(indexs[i] == index) {
                index--;
                stack.push(arr[i]);
            }
        }

        while (!stack.isEmpty()) {
            System.out.print(stack.pop() + " ");
        }
        System.out.println();
    }
}