[백준 14003] 가장 긴 증가하는 부분 수열 5 (JAVA)

문제

---

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

풀이

---

최장 증가 부분 수열(LIS, Longest Increasing Subsequence)을 이용하여 해결할 수 있습니다.

arr : [1, 2, 6, 4, 2, 5, 3, 7, 9]
dp : []
최장 증가 부분 수열 길이를 찾기 위해선 현재 값들을 저장하는 배열이 필요합니다.(dp 배열)

1) dp가 비어있으므로 바로 넣습니다.
dp [1]

2) 현재 dp의 가장 끝 값이랑 비교하여 2가 크므로 배열에 넣습니다.
dp [1, 2]

3) 6은 2보다 크므로 배열에 넣습니다.
dp [1, 2, 6]

4) 4가 6보다 작으므로 6자리에 4를 넣습니다.
dp [1, 2, 4]

5) 2는 2가 있으므로 2자리에 2를 넣습니다.
dp [1, 2, 4]

6) 4가 5보다 크므로 배열에 넣습니다
dp [1, 2, 4, 5]

7) 3이 4보다 작으므로 4자리에 3을 넣습니다
dp [1, 2, 3, 5]

8) 7이 5보다 크므로 배열에 넣습니다
dp [1, 2, 3, 5, 7]

9) 9가 7보다 크므로 배열에 넣습니다.
dp [1, 2, 3, 5, 7, 9]

dp 배열을 탐색할 때 선형탐색으로 진행하면 O(n^2), 이분탐색으로 진행하면 O(nlogn)의 시간복잡도가 발생합니다.

dp 배열의 길이를 통해 최장 증가 부분 수열의 길이를 찾을 수 있습니다. 그러나 dp의 있는 값이 LIS를 이루는 요소와는 다를 수 있습니다.
ex) 2, 4, 3, 5, 1, 8 => dp [1, 3, 5, 8]

요소를 찾기 위해서는 역추적 배열을 만들어 각각의 배열들을 어떤 dp 배열에 넣었는지 확인합니다.

1) 1은 dp 0번째 배열에 넣었으므로 0을 넣습니다.
[0]

2) 2는 1번째 배열에 넣었으므로 1을 넣습니다.
[0, 1]

3) 6은 2번째 배열에 넣었으므로 2를 넣습니다.
[0, 1, 2]

4) 4는 6자리에 들어갔으므로 2를 넣습니다.
[0, 1, 2, 2]

5) 2는 2자리에 들어갔으므로 1을 넣습니다.
[0, 1, 2, 2, 1]

6) 5는 3번째 배열에 넣었으므로 3을 넣습니다.
[0, 1, 2, 2, 1, 3]

7) 3은 4자리에 들어갔으므로 2를 넣습니다.
[0, 1, 2, 2, 1, 3, 2]

8) 7은 4번째 배열에 넣었으므로 4를 넣습니다.
[0, 1, 2, 2, 1, 3, 2, 4]

9) 9는 5번째 배열에 넣었으므로 5를 넣습니다
[0, 1, 2, 2, 1, 3, 2, 4, 5]

역추적 배열을 거꾸로 탐색하면서 5 -> 4 -> 3 -> 2 -> 1 -> 0 순으로 찾은 후 스택에 넣고 pop을 이용해 출력합니다.
arr : [1, 2, 6, 4, 2, 5, 3, 7, 9]
역추적 : [0, 1, 2, 2, 1, 3, 2, 4, 5]
정답 : [1, 2, 4, 5, 7, 9]

코드

---

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;
import java.util.StringTokenizer;

public class Main {

    public static int[] arr, save, index;
    public static int arrIndex = 0, pointer = 0;

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());
        arr = new int[N];
        save = new int[N];
        index = new int[N];

        StringTokenizer st = new StringTokenizer(br.readLine());
        int num = Integer.parseInt(st.nextToken());
        save[0] = num;
        arr[arrIndex] = num;
        index[arrIndex++] = 0;

        for (int i = 1; i < N; i++) {
            num = Integer.parseInt(st.nextToken());
            insert(num);
        }

        StringBuilder sb = new StringBuilder();
        sb.append(pointer + 1).append('\n');

        Stack<Integer> stack = new Stack<>();
        int idx = pointer;
        for (int i = N - 1; i >= 0; i--) {
            if (index[i] == idx) {
                stack.push(arr[i]);
                idx--;
            }
        }

        while (!stack.isEmpty()) {
            sb.append(stack.pop()).append(' ');
        }

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

    public static void insert(int num) {
        arr[arrIndex] = num;
        if (save[pointer] > num) {
            int i = binarySearch(num);
            save[i] = num;
            index[arrIndex] = i;
        } else if (save[pointer] < num) {
            save[++pointer] = num;
            index[arrIndex] = pointer;
        } else {
            index[arrIndex] = pointer;
        }
        arrIndex++;
    }

    public static int binarySearch(int num) {
        int left = -1, right = pointer;
        while (left + 1 < right) {
            int mid = (left + right) >> 1;

            if (save[mid] < num) left = mid;
            else right = mid;
        }

        return right;
    }
}