[백준/이분탐색] 14003번 가장 긴 증가하는 부분 수열 5 (JAVA)

문제

---

풀이

가장 긴 증가하는 부분 수열 2에서 LIS의 원소들도 출력하는 조건이 추가된 문제다.

이를 해결하기 위해, LIS를 만들었을 때 그 원소의 이전 원소를 저장하기 위한 before 배열을 추가로 선언했다. before에는 value가 아닌 index를 저장해야 한다. LIS의 모든 원소를 순서대로 방문하려면 재귀적으로 자신의 앞 원소를 호출해야 하고, 이 때 index가 필요하기 때문이다.

이처럼 index를 저장하기 위해 lis List에도 원소의 값이 아닌 arr에서의 index를 저장했다. lis의 활용과 업데이트 방식은 가장 긴 증가하는 부분 수열 2 문제와 동일한데, 저장하는 값을 원소의 value가 아닌 index로 하는 것이다.

알고리즘 동작 방식은 아래와 같다.

1. 가장 첫 번째 원소 arr[0]은
   • lis에 조건 없이 추가한다.
   • 이전 원소가 없다는 의미에서 before[0]에 -1을 저장한다.

2. arr[1]부터 arr[n-1]까지 탐색한다.
   • arr[i]가 lis의 최댓값보다 큰 경우
     • 앞선 어떠한 LIS 배열에 붙여도 상관이 없다.
     • before[i]를 lis의 최댓값의 index로 업데이트하고
     • lis에 i를 추가한다.
   • arr[i]가 lis의 최댓값보다 작은 경우
     • findIndex(i): lis에서 삽입 가능한 최대 index를 찾는다.
     • before[i]를 lis.get(replaceIndex-1)로 업데이트한다.
     • replaceIndex가 0이면 새로운 LIS의 첫 원소라는 뜻이므로 before[i]는 -1이다.
     • lis에 i를 삽입한다.

3. writeArr()에서 before[index]를 재귀적으로 호출하며 LIS를 순서대로 출력한다.

코드

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

public class Main {

    private static final int INITIAL = -1;

    private static int n;
    private static int[] arr;
    private static int[] before;
    private static List<Integer> lis = 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));

        parseInput(br);
        findLIS();
        writeAnswer(bw);

        br.close();
        bw.close();
    }

    private static void parseInput(BufferedReader br) throws IOException {
        n = Integer.parseInt(br.readLine());
        arr = new int[n];
        String[] line = br.readLine().split(" ");
        for (int i = 0; i < n; i++) arr[i] = Integer.parseInt(line[i]);
    }

    private static void findLIS() {
        before = new int[n];
        before[0] = INITIAL;
        lis.add(0);
        for (int i = 1; i < n; i++) {
            if (arr[i] > arr[lis.get(lis.size() - 1)]) {
                before[i] = lis.get(lis.size() - 1);
                lis.add(i);
            } else {
                int replaceIndex = findIndex(i);
                before[i] = (replaceIndex > 0 ? lis.get(replaceIndex - 1) : INITIAL);
                lis.set(replaceIndex, i);
            }
        }
    }

    private static int findIndex(int current) {
        int left = 0, right = lis.size() - 1, mid;
        while (left < right) {
            mid = (left + right) / 2;
            if (arr[current] > arr[lis.get(mid)]) left = mid + 1;
            else right = mid;
        }
        return (left + right) / 2;
    }

    private static void writeAnswer(BufferedWriter bw) throws IOException {
        bw.append(String.valueOf(lis.size())).append("\n");
        writeArr(bw, lis.get(lis.size() - 1));
    }

    private static void writeArr(BufferedWriter bw, int index) throws IOException {
        if (before[index] == INITIAL) {
            bw.append(String.valueOf(arr[index])).append(" ");
            return;
        }
        writeArr(bw, before[index]);
        bw.append(String.valueOf(arr[index])).append(" ");
    }
}