[백준 Baekjoon] 14003번 가장 긴 증가하는 부분 수열 5 - JAVA

백준 Baekjoon 14003번 가장 긴 증가하는 부분 수열 5 - JAVA

---

문제 풀이

가장 긴 증가하는 부분 수열 문제 중 5번째 문제이다. 1번 DP문제에서 2번 부터 이분 탐색을 적용하여 푸는 문제에서 점점 더 어려워진다. 문제 설명만 보면 이전 문제들과 차이가 없어 보이는데 부분 수열을 출력하는 것이 추가 되었다.

문제를 풀기 위해 배열 2개와 리스트 하나를 만들어 사용하였다.
arr 배열 : 입력 값을 저장
idx 배열 : 각 숫자의 증가 길이 저장
list : 가장 긴 증가하는 부분 수열을 저장, 길이를 알기 위해 사용

리스트 0번째에 음의 가장 작은 값을 저장하여 비교하는데 활용한다. 현재까지 저장 된 가장 긴 증가하는 부분 수열의 마지막 값과 새로 입력 받는 값을 비교하여 새로 입력 받은 값이 더 크면 리스트에 추가, 작은 경우 이분 탐색을 활용하여 저장 된 부분 수열 중 새로 입력 받은 값이 위치할 수 있는 자리를 찾아 해당 자리에 저장한다. 동시에 idx 배열에 가장 긴 증가하는 부분 수열에서 입력 값이 어느 번쨰에 저장되는 지(리스트에서 몇 번째인지)를 저장한다.

입력이 완료 되면 리스트의 길이가 가장 긴 부분 수열의 길이가 되며, 배열을 역으로 순회하며 해당 길이의 값을 idx에서 찾아 스택에 arr의 입력 값을 저장한다. 스택에 가장 긴 증가하는 부분 수열이 저장되면 하나씩 꺼내 출력해주면 된다.

소스 코드

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());

        int[] arr = new int[N];
        int[] idx = new int[N];

        List<Integer> list = new ArrayList<>();
        list.add(Integer.MIN_VALUE);

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

        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());

            if (list.get(list.size() - 1) < arr[i]) {
                list.add(arr[i]);
                idx[i] = list.size() - 1;
            } else {
                int left = 0, right = list.size() - 1;

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

                    if (list.get(mid) >= arr[i]) {
                        right = mid;
                    } else {
                        left = mid + 1;
                    }
                }

                list.set(right, arr[i]);
                idx[i] = right;
            }
        }

        StringBuilder sb = new StringBuilder();
        sb.append(list.size() - 1).append("\n");

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

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

        System.out.println(sb);
    }
}