문제 풀이(55)

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

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


public class Main {

    static int N, maxLength;
    static int[] A;
    static int[] B;
    static int[] D;
    static int[] ans;  
    public static void main(String[] args) throws IOException {
        
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    
        N = Integer.parseInt(br.readLine());

        B = new int[N + 1];

        D = new int[N + 1];

        A = new int[N + 1];

        ans = new int[N + 1];

        StringTokenizer st = new StringTokenizer(br.readLine());

        for (int i = 1; i <= N; i++) {
            A[i] = Integer.parseInt(st.nextToken());
        }

        int index;

        maxLength = 1;

        B[maxLength] = A[1];

        D[1] = 1;


        for (int i = 2; i <= N; i++) {
            
            if (B[maxLength] < A[i]) {
                B[++maxLength] = A[i];
                D[i] = maxLength;
            }else{
                index = function(1, maxLength , A[i]);
                B[index] = A[i];
                D[i] = index;
            }
        }

        System.out.println(maxLength);

        index = maxLength;

        int x = B[maxLength] + 1;

        for (int i = N; i >= 1; i--) {
            
            if (D[i] == index && A[i] < x ) {
                
                ans[index] = A[i];

                x = A[i];

                index--;
            }

        }

        for (int i = 1; i <= maxLength; i++) {
            System.out.print(ans[i]+" ");
        }
    }

    public static int function(int left , int right, int x)
    {
        int res = right + 1;

        while (left <= right) {
            int mid = (left + right) / 2;

            if (B[mid] >= x) {
                res = mid;
                right = mid - 1;
            }else{
                left = mid + 1;
            }
        }

        return res;
    }
}

LIS 계산:
B[1]에 A[1]을 할당하고 D[1]에 1을 할당하여 초기화한다.
각 A[i]에 대해 if (B[maxLength] < A[i])를 확인하여 A[i]가 현재 LIS의 마지막 값보다 큰 경우, LIS 길이를 증가시키고 B와 D 배열을 업데이트한다.
그렇지 않으면 binarySearch와 같은 기능을 하는 function 메소드를 사용하여 A[i]를 삽입할 적절한 위치를 찾아 B 배열을 업데이트한다.

maxLength는 가장 긴 증가하는 부분 수열의 길이이다.
for 루프를 사용하여 N에서 1까지 역으로 순회하면서 ans[] 배열을 채운다. 이 배열은 A[]의 각 요소가 해당 LIS에 포함될 경우 거꾸로 추적하여 저장한다.
마지막으로 ans[] 배열의 요소를 1부터 maxLength까지 순서대로 출력하여 실제 LIS를 출력한다.

function 메소드:
이진 검색 알고리즘을 사용하여 B 배열에서 주어진 값 x보다 크거나 같은 값의 인덱스를 찾는다.
이 메소드는 B 배열에서 A[i]를 삽입할 위치를 결정하는 데 사용된다.