백준 14003 (가장 긴 증가하는 부분 수열 5) - java

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

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

 

문제 

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.

수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.

가장 긴 증가하는 부분 수열의 길이와 부분 수열을 구하라

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다.

둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (-1,000,000,000 ≤ Ai ≤ 1,000,000,000)

 

유형 : LIS(이진 탐색) + LIS 역추적

 

접근 방식

• 수열의 크기를 통해 우리는 DP방법 : O(N^2)이 아닌 이진 탐색 : O(NlogN)을 사용해야 함을 알 수 있다.
• 이 문제에서 중요한 것은 LIS의 길이를 구하는 것이 아닌 LIS 결과를 구하는 것이다.
  • 이진 탐색을 하는 동안 우리는 임의의 배열의 값을 변경한다.
  • 이러한 배열이 LIS를 만족한다 볼 수 있을까 ? -> NO !!!!!!!!!
• 변경을 진행하는 배열
  • 임의의 배열의 상태는, "증가하는 부분 수열"의 규칙에 어긋나지 않게, LIS 배열의 상태를 보면서, 최적의 위치를 찾으면서 값을 재설정하거나, 값을 삽입해 주는 것이다.
  • 해당 인덱스의 구간 (전 인덱스와 다음 인덱스 사이의 값임은 자명)은 만족하지만 값 자체가 결과를 만족하지는 않는다.
• LIS 역추적
  • past 배열을 하나 만들고 해당 index(1 - n)에 만족하는 결과 배열의 index를 저장한다.
  • 그리고 n - 1 순서로 역순 탐색하면서 결과를 완성한다.

전체 코드

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

public class Main {
    static int n = 0;
    static int[] num;
    static int[] past;
    static int[] result;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        n = Integer.parseInt(st.nextToken());

        num = new int[n];
        past = new int[n];
        result = new int[n];

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

        result[0] = num[0];
        int i = 1;
        int j= 0;

        int maxIdx= 0;

        while(i < n){

            if(result[j] < num[i]){
                result[j+1] = num[i];
                past[i] = j + 1;
                j = j + 1;

            }else{
                int idx = bs(0,j,num[i]);
                result[idx] = num[i];
                past[i] = idx;
            }

            i = i + 1;

        }

        Stack<Integer> stack = new Stack<>();
        StringBuilder sb = new StringBuilder();
        sb.append(j+1+"\n");

        int find = j;
        for(int k= n-1;k>=0;k--){
            if(find == past[k]){
                stack.push(num[k]);
                find = find - 1;
            }
        }

        while(!stack.isEmpty()){
            sb.append(stack.pop()+" ");
        }
        sb.append("\n");

        System.out.print(sb);
        br.close();
    }

    static void print(){
        for(int i=0;i<n;i++){
            System.out.print(past[i]+" ");
        }
        System.out.println();
    }

    static void print2(){
        for(int i=0;i<n;i++){
            System.out.print(result[i]+" ");
        }
        System.out.println();
    }

    static int bs(int l,int r,int t){
        int mid;

        while(l < r){
            mid = (l + r) / 2;

            if(result[mid] < t){
                l = mid + 1;
            }else{
                r = mid;
            }

        }

        return r;
    }
}