BOJ_14003_가장 긴 증가하는 부분 수열 5 (Java)

[Platinum V] 가장 긴 증가하는 부분 수열 5 - 14003

문제 링크

성능 요약

메모리: 155836 KB, 시간: 736 ms

분류

이분 탐색, 가장 긴 증가하는 부분 수열: O(n log n)

제출 일자

2025년 1월 16일 02:53:33

문제 설명

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

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

입력

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

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

출력

첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다.

둘째 줄에는 정답이 될 수 있는 가장 긴 증가하는 부분 수열을 출력한다.

문제 풀이

BOJ_12738_가장 긴 증가하는 부분 수열 3 (Java) 와 이어지는 문제다.

어떻게 배열을 구상해야할지 참고했고, 이분탐색은 남들 코드와는 다르게 항상 작성하던데로 left<=right와 res를 반환하는 형태로 고민하여 작성해보았다.

코드

/**
 * Author: nowalex322, Kim HyeonJae
 */

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

public class Main {
    static BufferedReader br;
    static BufferedWriter bw;
    static StringTokenizer st;
    static StringBuilder sb = new StringBuilder();
    int N;
    static int[] arr, dp, LIS;
    public static void main(String[] args) throws Exception {
        new Main().solution();
    }

    public void solution() throws Exception {
        br = new BufferedReader(new InputStreamReader(System.in));
//        br = new BufferedReader(new InputStreamReader(new FileInputStream("src/main/java/BOJ_12015_가장긴증가하는부분수열2/input.txt")));
        bw = new BufferedWriter(new OutputStreamWriter(System.out));
        N = Integer.parseInt(br.readLine());
        arr = new int[N+1];
        LIS = new int[N+1];
        dp = new int[N+1];
        st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
        int idx = 1;
        LIS[1] = arr[1];
        dp[1] = 1;

        int maxLen = 1;
        for(int i = 2; i <= N; i++) {
            if(arr[i] > LIS[idx]) {
                LIS[++idx] = arr[i];
                dp[i] = idx;
            }
            else{
                int pos = binarySearch(1, idx, arr[i]);
                LIS[pos] = arr[i];
                dp[i] = pos;
            }
            maxLen = Math.max(maxLen, dp[i]);
        }
        sb.append(maxLen).append("\n");
        ArrayList<Integer> res = new ArrayList<>();
        for(int i = N; i >= 1; i--) {
            if(dp[i] == maxLen) {
                res.add(arr[i]);
                maxLen--;
            }
        }
        Collections.reverse(res);
        for(int num : res) {
            sb.append(num).append(" ");
        }
        bw.write(sb.toString());
        bw.flush();
        bw.close();
        br.close();
    }

    private int binarySearch(int left, int right, int target) {
        int res = 0;
        while(left <= right){
            int mid = left + (right - left) / 2;
            if(LIS[mid] < target){
                left = mid + 1;
            }
            else {
                res = mid;
                right = mid - 1;
            }
        }
        return res;
    }
}