[알고리즘] Java / 백준 / 가장 긴 증가하는 부분 수열 5 / 14003

[알고리즘] Java / 백준 / 가장 긴 증가하는 부분 수열 5 / 14003

문제

문제 링크

접근 방식

이분 탐색을 이용하여 LIS 문제를 푸는 과정에서 숫자 배열(arr)의 수가 LIS 배열에 들어가는 인덱스를 rec 배열에 저장한다.

// 40, 20, 10, 30, 40, 20, 50 의 경우
// LIS = {10, 20, 40, 50, 0, 0} -> size = 4
// rec = {0, 0, 0, 1, 2, 1, 3}

그 후 rec 배열의 뒤에서 부터 시작하여 3, 2, 1, 0을 선택하면 가장 긴 증가하는 부분수열의 원소를 구할 수 있다.

// ans = {10, 30, 40, 50}

코드

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

public class Main_14003 {

	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int[] arr = new int[N];
		int[] LIS = new int[N];
		int[] rec = new int[N];
		for(int i=0;i<N;i++) arr[i] = Integer.parseInt(st.nextToken()); 
		
		
		int size = 0;
		
        for (int i=0; i < N; i++) {
        	
            int temp = Arrays.binarySearch(LIS, 0, size, arr[i]);
            if(temp < 0) temp = Math.abs(temp)-1;
            rec[i] = temp;
            LIS[temp] = arr[i];

            if (size == temp) {
                size++;
            }
        }
        
        int answer[] = new int[size];
        int answerIdx = size-1;
        for(int i=N-1;i>=0;i--) {
        	if(rec[i] == answerIdx) answer[answerIdx--] = arr[i];
        }
        
        StringBuilder sb = new StringBuilder();
        sb.append(size+"\n");
        for(int i=0;i<size;i++) {
        	sb.append(answer[i]+" ");
        }
        System.out.println(sb);
       
	}
	
	
}