백준 12015 Java: LIS 길이를 Lower Bound로 O(N log N)에 구하기

백준 12015를 풀던 2022년 5월에는 이진 탐색에 심리적인 거부감이 있었다. 반나절 정도 접근을 고민한 뒤 list를 이용한 풀이를 찾아봤고, 그대로 끝내지 않고 array 방식으로 다시 구현했다. 당시 제출에서는 list 풀이가 756ms, array 풀이가 592ms였지만 한 번의 채점 결과를 일반적인 성능 benchmark로 보지는 않는다.

이 문제에서 가져갈 핵심은 각 길이의 증가 부분 수열이 가질 수 있는 가장 작은 마지막 값을 tails에 유지하는 것이다.

tails의 의미

tails[i]를 길이가 i + 1인 strictly increasing subsequence 중 현재까지 찾은 최소 마지막 값이라고 정의한다.

새 값 value가 들어오면 다음 두 경우다.

• value가 현재 모든 tail보다 크면 뒤에 붙여 LIS 후보 길이를 1 늘린다.
• 그렇지 않으면 value 이상인 첫 위치를 찾아 그 값을 value로 교체한다.

교체는 기존 subsequence를 실제로 고치는 동작이 아니다. 같은 길이에서 더 작은 tail을 남겨 이후 더 많은 값을 붙일 가능성을 여는 요약 정보다.

5 10 15 1 2 3을 따라가 보기

입력	tails
5	[5]
10	[5, 10]
15	[5, 10, 15]
1	[1, 10, 15]
2	[1, 2, 15]
3	[1, 2, 3]

마지막 tails의 길이는 3이다. 하지만 [1, 2, 3]이 우연히 실제 subsequence인 이 예와 달리, 일반적으로 tails 배열 자체가 원본에서 뽑은 LIS를 보장하지는 않는다. 문제는 길이만 요구하므로 충분하다. 실제 수열을 복원하려면 predecessor와 각 원소가 들어간 position을 추가로 기록해야 한다.

Lower Bound가 필요한 이유

strictly increasing LIS에서는 value와 같은 값이 길이를 늘리면 안 된다. 그래서 첫 번째 tails[index] >= value인 위치, 즉 lower bound를 찾는다.

tails = [1, 3, 7]
value = 3
lower bound index = 1
result = [1, 3, 7]

upper bound처럼 value보다 큰 첫 위치를 찾으면 duplicate가 길이를 늘리는 non-decreasing subsequence 문제와 섞일 수 있다.

Java 풀이

입력 크기가 최대 1,000,000이므로 primitive array와 buffered input을 사용했다. 원래 code의 0 padding은 이 문제의 값이 양수라 동작하지만, 아래 구현은 input 값 범위에 기대지 않는다.

import java.io.BufferedInputStream;
import java.io.IOException;

public class Main {
    public static void main(String[] args) throws Exception {
        FastScanner scanner = new FastScanner();
        int size = scanner.nextInt();
        int[] tails = new int[size];
        int length = 0;

        for (int index = 0; index < size; index++) {
            int value = scanner.nextInt();
            int position = lowerBound(tails, length, value);
            tails[position] = value;

            if (position == length) {
                length++;
            }
        }

        System.out.println(length);
    }

    private static int lowerBound(int[] values, int length, int target) {
        int left = 0;
        int right = length;

        while (left < right) {
            int middle = left + (right - left) / 2;
            if (values[middle] >= target) {
                right = middle;
            } else {
                left = middle + 1;
            }
        }
        return left;
    }

    private static final class FastScanner {
        private final BufferedInputStream input =
            new BufferedInputStream(System.in);
        private final byte[] buffer = new byte[1 << 16];
        private int index;
        private int size;

        int nextInt() throws IOException {
            int value = 0;
            int current;
            do {
                current = read();
            } while (current <= ' ');

            while (current > ' ') {
                value = value * 10 + current - '0';
                current = read();
            }
            return value;
        }

        private int read() throws IOException {
            if (index >= size) {
                size = input.read(buffer);
                index = 0;
                if (size < 0) {
                    return -1;
                }
            }
            return buffer[index++];
        }
    }
}

왜 길이가 보존되나

tails[index]를 더 작은 값으로 교체해도 이미 만든 길이 index + 1은 사라지지 않는다. 그 길이의 increasing subsequence가 존재한다는 사실은 유지되고, 마지막 값만 더 유리해진다.

반대로 가장 큰 tail보다 큰 값이 들어오면 기존 가장 긴 후보 뒤에 붙일 수 있으므로 길이가 정확히 1 늘어난다. 입력 순서대로 이 규칙을 반복하면 tails 길이가 지금까지 본 prefix의 LIS 길이와 같다.

복잡도와 확인할 입력

원소마다 길이 L의 tails에서 binary search한다.

• 시간 복잡도: O(N log N)
• 공간 복잡도: O(N)

[1]                 -> 1
[1, 2, 3, 4]        -> 4
[4, 3, 2, 1]        -> 1
[2, 2, 2]           -> 1
[10, 20, 10, 30, 20, 50] -> 4

O(N²) dynamic programming으로 먼저 정의를 확인한 뒤 작은 random array에서 두 answer를 비교하면 lower-bound 구현의 off-by-one을 찾기 좋다.

기본 LIS DP는 백준 11053 Java, 증가·감소 수열을 연결하는 문제는 백준 11054 바이토닉 수열에서 이어서 볼 수 있다.

참고 자료

• 백준 12015 가장 긴 증가하는 부분 수열 2