백준 14003번 : 가장 긴 증가하는 부분 수열 5 [자바]

🧫 문제 분석

 

✔️ 출처

가장 긴 증가하는 부분 수열 5 플래티넘 5

 

📖 문제

 

LIS 시리즈중 마지막 문제

기존 이분탐색 LIS에 역추적이 추가된 문제다.

 

실제 LIS를 구하려면 LIS를 기록해야한다.

단순히 덮어씌운 값이 아닌 실제 증가하는 부분수열을 구해야하기에

이전 값의 위치를 기록할 필요가 있다.

 

예제를 보면

 

10 20 10 30 20 50 이 입력되는데

여기서 실제 LIS는 

 

10 20 10 30 20 50

이렇게 된다. 그럼 어떻게 추적을 해야하나

 

LIS 내에서 이분탐색을 하면서 새로운 값 추가가 아니면 

기존 LIS 원소 내에 덮어씌운다. 

 

때문에 LIS에 기록될 때 LIS에 기록된 위치에서 이전 위치의 값을 기록하는 것이다.

단순히 -1~순차적으로 올릴 수 있지만 

여기서는 prev만으로 바로 위치를 찾아서 값을 찾을 수 있게 idx 배열도 사용한다. 

---

🔅 문제 풀이

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

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        int N = Integer.parseInt(br.readLine());
        int[] arr = new int[N];
        int[] LIS = new int[N];
        int[] prev = new int[N]; // LIS[i]가 arr의 어느 인덱스에서 왔는지
        int[] LISIdx = new int[N]; // 	LIS[i] 이전 LIS 원소 인덱스

        Arrays.fill(prev, -1);

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

        LIS[0] = arr[0];
        int size = 1;
        for (int i = 1; i < N; i++) {

            // LIS에서 마지막 값보다 큰 값이라면 뒤에 추가
            if (LIS[size - 1] < arr[i]) {
                LIS[size] = arr[i];
                LISIdx[size] = i;
                prev[i] = LISIdx[size - 1]; // dp내 이전 값의 idx를 prev에 저장
                size++;
                continue;
            }

            // 이분 탐색으로 증가하는 부분수열에서 적절한 위치를 탐색
            int left = 0, right = size - 1;
            while (left < right) {

                int mid = (left + right) >>> 1;

                if (LIS[mid] < arr[i]) {
                    left = mid + 1;
                } else {
                    right = mid;
                }
            }

            LIS[left] = arr[i];
            LISIdx[left] = i;
            if (left > 0) {
                prev[i] = LISIdx[left - 1];
            }
        }


        Stack<Integer> stack = new Stack<>();
        sb.append(size).append("\n");

        // dp의 마지막 값의 실제 idx를 꺼냄
        int idx = LISIdx[size-1];

        // prev로 역추적
        while (size > 0) {
            stack.push(arr[idx]);
            idx = prev[idx];
            size--;
        }

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

        System.out.println(sb.toString());
    }
}

 

 

 

❗ 오답노트 / 필요한 지식

1.