[BOJ] 14003 : 가장 긴 증가하는 부분 수열 5(Java)

문제 링크

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

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

---

💡 풀이

기존 가장 긴 증가하는 부분 수열 즉, LIS을 응용해야 하는 문제입니다. 

LIS - DP

LIS를 해결하는 가장 간편한 방법은 DP를 이용하는 것입니다. 주어진 숫자 배열에서 인덱스를 한 칸씩 늘려가며 확인하는 방법입니다. 하지만, 이 방법은 2중 반복문을 사용하기 때문에 $O(N^2)$의 시간복잡도를 가집니다. 따라서, 해당 문제는 입력 N의 최댓값이 1,000,000이기 때문에, 시간초과가 발생하게 됩니다. 

LIS - 이분 탐색(Binary Search)

따라서, 대게 LIS를 해결할 때 이분 탐색을 이용합니다. 해당 방법에서는 LIS를 기록하는 배열을 하나 더 두고, 원래 수열에서 각 원소에 대해 LIS 배열 내에서의 위치를 찾습니다. 이 위치를 찾는 과정에서 이분 탐색을 이용하기 때문에 시간복잡도를 $O(NlogN)$으로 줄일 수 있습니다.

간단한 예시를 통해 알아봅시다.

주어진 배열의 첫 번째 원소를 LIS를 기록하는 새로운 배열 첫 번째 인덱스에 추가합니다. 

다음 인덱스의 수 5는 아래 배열의 마지막 수인 1보다 크기 때문에, 뒤쪽에 추가해줍니다. 

다음 인덱스의 수 4는 아래 배열의 마지막 수인 5보다 작습니다. 따라서, 이분 탐색을 통해 아래 배열에서 4가 들어갈 위치를 찾아서 배열을 갱신해주는 것입니다. 4가 들어갈 위치는 새로운 배열 중 해당 값보다 작은 최댓값입니다.

다음 인덱스의 수 2는 마찬가지로 아래 배열의 마지막 수인 4보다 작습니다. 따라서, 이분 탐색을 통해 아래 배열에서 2가 들어갈 위치를 찾아 갱신합니다. 

이후 3과 8은 배열의 마지막 수인 2보다 크기 때문에 뒤에 추가해줍니다. 

위와 마찬가지로 6은 8보다 작기 때문에 이분 탐색을 통해 아래 배열에 추가해줍니다. 

7과 9는 6보다 크기 때문에 뒤에 추가해줍니다. 

현재 수인 3을 보면 아래 배열의 마지막 수인 9보다 작습니다. 따라서, 이분 탐색을 통해 아래 배열에 3이 들어갈 위치를 찾습니다. 그렇다면 3이 들어가게 될 곳은 위 그림에서 표신된 붉은색 공간일 것입니다(기존에 "3"이 있던 곳).

위 방법에 따라 끝까지 진행하면 새로운 배열이 다음과 같이 완성되게 됩니다. 이 새로운 배열의 길이가 바로 LIS의 길이가 됩니다. 

즉, 

기존 수열의 현재 원소를 아래 새로운 배열에 넣어 LIS를 유지하려고 할 때, 그 최적의 위치를 찾는 방식

으로 동작하게 되는 것입니다. 

 

하지만, 주의해야 할 점이 있습니다.

위 방식은 기존 수열에서 LIS의 길이를 찾는 방식이지, 최종적인 LIS 수열을 찾는 것이 아닙니다!

실제로 위 예시를 통해 비교해보면, 이분 탐색을 통해 찾은 새로운 배열은 `[1, 2, 3, 4, 5, 9]`이지만, 이는 기존 배열의 부분 수열이 아닙니다. 실제 LIS의 수열은 `[1, 2, 3, 6, 7, 9]`가 됩니다. 

 

정리해보면, 이분 탐색만을 이용한 LIS 해결 방식은 LIS의 길이만 구할 수 있을 뿐, 실제 부분 수열을 구하는데에는 한계가 존재합니다. 

 

해당 "가장 긴 증가하는 부분 수열 5" 문제는 이 LIS의 수열을 구하는 것이기 때문에, 추가적인 작업이 필요합니다. 

 

LIS 수열 찾기 - 이분 탐색 + Stack

LIS의 수열을 찾기 위해 사용할 자료 구조는 Stack(스택)입니다. 왜 Stack을 이용하는지는 차차 설명하겠습니다. 

 

우선, Stack의 인자로 사용될 객체를 하나 생성합니다. 

static class Node {
    int value; // 값
    int index; // 해당 값의 인덱스

    Node(int value, int index) {
        this.value = value;
        this.index = index;
    }
}

`value`는 배열에서 원소의 값이고, `index`는 해당 원소의 배열 인덱스 값입니다. 

 

그리고, 기존에 만든 새로운 배열을 새로운 "Stack" 배열로 만들어 줄 것입니다.

static Stack<Node>[] LISStack;

 

이분 탐색을 이용해 현재 원소가 들어갈 위치를 찾는 것은 똑같지만, 새로운 배열의 해당 인덱스의 값과 교체해주는 것이 아닌 Stack에 push하는 방식으로 Stack 배열을 만들어 줄 것입니다. 

...
 // 결과를 넣을 Stack List
LISStack = new Stack[N];
int curIndex = 0; // 진행된 Stack 배열의 인덱스

// 처음 초기값 넣기
LISStack[0] = new Stack<>();
LISStack[0].push(new Node(numbers[0], 0));

// 각 자리에 올 수 있는 숫자들을 stack 에 넣기
for (int i = 1; i < N; i++) {
    int curNum = numbers[i];
    // 현재 결과 리스트의 마지막 인덱스보다 큰 경우
    if (LISStack[curIndex].peek().value < curNum) {
        LISStack[++curIndex] = new Stack<>();
        LISStack[curIndex].push(new Node(curNum, i));
        continue;
    }
    // 아닌 경우, 이분 탐색을 통해 들어갈 수 있는 위치 찾기
    int findIndex = binarySearch(curNum, 0, curIndex);
    LISStack[findIndex].push(new Node(curNum, i));
}
...
// 현재 찾는 수가 들어갈 수 있는 위치 찾기
static int binarySearch(int target, int low, int high) {
    while (low < high) {
        int mid = (low + high) / 2;

        if (target > LISStack[mid].peek().value) {
            low = mid + 1;
        } else {
            high = mid;
        }
    }
    return high;
}

위에서 설명한 이분 탐색 방식을 거쳐 Stack 배열에 삽입하는 과정을 수행하면 최종적인 Stack 배열의 결과는 위의 그림과 같을 것입니다. 이때, Stack 안의 원소는 `Node`이며 `[원소값, Index]`로 구성되어 있습니다. 

 

이제 저희가 확인해야 하는 것은 새로운 Stack 배열의 마지막 인덱스부터 첫 인덱스 순서로(반대로) `Node` 객체의 두 번째 원소인 `Index`를 비교해 나아갈 것입니다. 

예를 들어, 현재 Stack 배열의 마지막 원소는 [9, 8]입니다. 즉, 9라는 숫자와 이 숫자의 기존 배열에서 인덱스가 8이라는 의미입니다. 이 값과 Stack 배열에서 바로 앞의 Stack과 비교를 합니다. 이 Stack의 Top의 값은 [5, 11]입니다. 이때, 숫자 5의 인덱스가 11로 [9, 8]에서 인덱스 8보다 앞선다면, 수열을 만들 수 없습니다. 

따라서, 그 다음 원소인 [7, 7]을 pop하여 확인 합니다. 인덱스 7은 8보다 낮기 때문에 수열을 생성할 수 있습니다. 

 

이와 같은 과정으로 앞 원소와의 인덱스를 비교하며 수열을 만들어 나아갈 수 있습니다. 

// LIS 수열의 결과를 담을 배열
int[] result = new int[curIndex + 1];
// 완성된 결과 stack 배열의 마지막 인덱스부터 탐색 시작
Node prev = LISStack[curIndex].pop();
result[curIndex] = prev.value;

for (int index = curIndex - 1; index >= 0; index--) {
    Node cur;
    while (true) {
        cur = LISStack[index].pop();
        if (cur.index < prev.index) {
            result[index] = cur.value;
            break;
        }
    }
    prev = cur;
}

 

위 과정을 수행하고 result에 담긴 수열을 출력해주면 됩니다.

 

전체 코드

전체적인 코드는 다음과 같습니다. 

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

class Q14003 {
    static int N;
    static int[] numbers;
    static Stack<Node>[] LISStack;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st;

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

        // 결과를 넣을 Stack List
        LISStack = new Stack[N];
        int curIndex = 0;

        // 처음 초기값 넣기
        LISStack[0] = new Stack<>();
        LISStack[0].push(new Node(numbers[0], 0));

        // 각 자리에 올 수 있는 숫자들을 stack 에 넣기
        for (int i = 1; i < N; i++) {
            int curNum = numbers[i];
            // 현재 결과 리스트의 마지막 인덱스보다 큰 경우
            if (LISStack[curIndex].peek().value < curNum) {
                LISStack[++curIndex] = new Stack<>();
                LISStack[curIndex].push(new Node(curNum, i));
                continue;
            }
            // 아닌 경우, 이분 탐색을 통해 들어갈 수 있는 위치 찾기
            int findIndex = binarySearch(curNum, 0, curIndex);
            LISStack[findIndex].push(new Node(curNum, i));
        }

        // 결과 찾기
        int[] result = new int[curIndex + 1];
        // 완성된 결과 stack 배열의 뒷 인덱스부터 탐색 시작
        Node prev = LISStack[curIndex].pop();
        result[curIndex] = prev.value;
        for (int index = curIndex - 1; index >= 0; index--) {
            Node cur;
            while (true) {
                cur = LISStack[index].pop();
                if (cur.index < prev.index) {
                    result[index] = cur.value;
                    break;
                }
            }
            prev = cur;
        }

        // 결과 출력하기
        sb.append(curIndex + 1).append("\n"); // curIndex 는 인덱스 값이기 때문에 +1 해야 개수가 된다.
        for (int number : result) {
            sb.append(number).append(" ");
        }

        System.out.println(sb);
    }

    // 현재 찾는 수가 들어갈 수 있는 위치 찾기
    static int binarySearch(int target, int low, int high) {
        while (low < high) {
            int mid = (low + high) / 2;

            if (target > LISStack[mid].peek().value) {
                low = mid + 1;
            } else {
                high = mid;
            }
        }
        return high;
    }

    static class Node {
        int value; // 값
        int index; // 해당 값의 인덱스

        Node(int value, int index) {
            this.value = value;
            this.index = index;
        }
    }
}