[Java] BOJ/백준 14003번 가장 긴 증가하는 부분 수열 5

[문제]

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

14003번: 가장 긴 증가하는 부분 수열 5

 

[풀이]

[Java] BOJ/백준 12738번 가장 긴 증가하는 부분 수열 3

[Java] BOJ/백준 14002번 가장 긴 증가하는 부분 수열 4

이 문제는 백준 12738번 가장 긴 증가하는 부분 수열 3 문제의 이분 탐색에 백준 14002번 가장 긴 증가하는 부분 수열 4 문제의 역추적 개념만 추가된 것이기 때문에 이 두 문제를 미리 풀어보는 것이 좋다.

 

문제에 나온 예제를 seq 배열에 담고 preLIS 리스트에 백준 12015번 가장 긴 증가하는 부분 수열 2 에서 구한 것처럼 LIS 원소를 최대한 많이 배치할 수 있도록 이분 탐색으로 원소를 갱신해 저장한다. 주의할 점은 preLIS 라는 이름에서부터 유추할 수 있듯이 이분 탐색을 통해 만들어진 preLIS는 LIS의 최대길이를 구하는 역할을 할 뿐 정확하게 LIS 원소를 가진 것은 아니다.

 

따라서 이 문제에서는 추가적으로 자신이 LIS 수열의 몇 번째 인덱스인지를 기록하는 preIndex 배열을 사용해야 한다.

 

주어진 수열이 {10, 20, 30, 15, 25, 50, 40} 이고 preLIS에 seq[0]값이 추가된 상황이라면

1️⃣ i가 1일 때

seq[1] = 20은 preLIS의 제일 큰 값인 10보다 크기 때문에 preLIS에 20을 추가해 preLIS = {10, 20}이 된다.

preIndex[1]에 (현재 preLIS 사이즈: 2 - 1)을 갱신한다.

 

2️⃣ i가 2일 때

seq[2] = 30은 preLIS의 제일 큰 값인 20보다 크기 때문에 preLIS에 30을 추가해 preLIS = {10, 20, 30}이 된다.

preIndex[2]에 (현재 preLIS 사이즈:3 - 1)을 갱신한다.

 

3️⃣ i가 3일 때

seq[3] = 15은 preLIS의 제일 큰 값인 30보다 작기 때문에 15보다 큰 수 중 가장 차이가 적게 나는 20과 교체한다.

preIndex[3]은 교체한 20의 preIndex 값(1)으로 갱신한다.

 

이런 식의 과정을 거치게 되면 아래와 같은 결과가 나오고 LIS의 최대길이(preLIS의 사이즈)를 알 수 있다.

 

preIndex 배열의 n - 1부터 0까지 값이 3인 인덱스를 찾고, 찾은 이후에는 2인 인덱스, 1인 인덱스를 차례대로 찾아 해당하는 값을 Stack에 넣고 마지막엔 pop 연산을 통해 출력한다.

 

[코드]

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
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));
        StringBuilder sb = new StringBuilder();
        int n = Integer.parseInt(br.readLine());
        int[] seq = new int[n];
        int[] preIndex = new int[n];

        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) seq[i] = Integer.parseInt(st.nextToken());

        ArrayList<Integer> preLIS = new ArrayList<>();
        preLIS.add(seq[0]);
        for (int i = 1; i < n; i++) {
            int key = seq[i];

            if (preLIS.get(preLIS.size() - 1) < key) {
                preLIS.add(key);
                preIndex[i] = preLIS.size() - 1;
            } else {
                int low = 0;
                int high = preLIS.size() - 1;
                while (low < high) {
                    int mid = (low + high) / 2;
                    if (preLIS.get(mid) >= key) high = mid;
                    else low = mid + 1;
                }
                preLIS.set(high, key);
                preIndex[i] = high;
            }
        }
        sb.append(preLIS.size() + "\n");

        Stack<Integer> stack = new Stack<>();
        int index = preLIS.size() - 1;
        for (int i = n - 1; i >= 0; i--){
            if (preIndex[i] == index){
                index--;
                stack.push(seq[i]);
            }
        }
        while (!stack.isEmpty()) sb.append(stack.pop() + " ");
        System.out.println(sb);
    }
}