P.14003 가장 긴 증가하는 부분 수열 5

코드

import java.io.*;
import java.util.ArrayList;
import java.util.Arrays;

public class Main {

    static int n;
    static int[] arr;
    static int[] idx;
    static ArrayList<Integer> seq = new ArrayList<>();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        n = Integer.parseInt(br.readLine());
        arr = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        seq.add(arr[0]);
        idx = new int[n];
        idx[0] = 0;
        for (int i = 1; i < n; i++) {
            if (seq.get(seq.size() - 1) < arr[i]) {
                seq.add(arr[i]);
                idx[i] = seq.size() - 1;
            }
            else idx[i] = binarySearch(arr[i]);
        }

        int curIdx = seq.size() - 1;
        int[] ans = new int[seq.size()];
        for (int i = n - 1; i >= 0; i--) {
            if (idx[i] == curIdx) {
                ans[curIdx] = arr[i];
                curIdx--;
            }
        }

        bw.write(seq.size() + "\n");
        for (int i = 0; i < seq.size(); i++) bw.write(ans[i] + " ");
        bw.flush();
    }

    private static int binarySearch(int num) {
        int start = 0, end = seq.size() - 1;
        while (start < end) {
            int mid = (start + end) / 2;

            if (seq.get(mid) < num) start = mid + 1;
            else end = mid;
        }
        seq.set(end, num);

        return end;
    }
}

코드 설명

기본적인 알고리즘은 다음 글에 있다.

2023.09.10 - [코딩테스트/백준] - P.12015 가장 긴 증가하는 부분 수열 2

P.12015 가장 긴 증가하는 부분 수열 2

 

해당 알고리즘에서는 정답으로 추정되는 수열이 계속 변화하기 때문에 가장 긴 증가하는 부분 수열을 구할 수 없다.

정답으로 추정되는 수열을 담는 배열은 오직 이 가장 긴 증가하는 부분 수열의 최장 길이만을 구하는데 사용되기 때문이다.

 

여기에 각각의 수가 갖는 위치를 저장하는 배열을 추가한다.

만약 예시가 다음과 같다면,

10 20 10 30 20 50

arr	10	20	10	30	20	50
idx	0	1	0	2	1	3

idx배열은 위와 같은 결과를 가지게 된다.

따라서 arr의 마지막 원소부터 앞으로 거꾸로 순회를 하면서 가장 긴 증가하는 부분 수열을 찾을 수 있다.

 

처음, 가장 긴 증가하는 부분 수열의 길이는 3이므로 50을 저장하고,

다음으로 idx가 2인 30을 저장한다.

이후 idx가 1인 20을 저장하고, 마지막으로 0인 10을 저장한다.