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

[문제]

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

12015번: 가장 긴 증가하는 부분 수열 2

 

 

[풀이]

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

해당 문제를 풀기 전 미리 풀어보는 것이 좋다.

이 문제와 위에 첨부한 문제와의 유일한 다른 점은 입력받는 배열의 길이가 1000배 더 길어 일반 DP 방식으로 풀면 시간초과가 발생한다.

따라서 이 문제는 DP가 아닌 이분 탐색으로 풀어야 한다는 것을 알 수 있다.

- DP : O(n^2)

- 이진탐색 : O(nlogn)

---

LIS의 핵심은, 원소가 증가해야 하며, 그 길이가 최대여야 한다는 것이다.

LIS의 길이가 최대이기 위해서는 상호 원소 간의 값의 차이가 작아야 한다.

 

입력된 값의 처음부터 순차적으로 검사를 할 경우 아래와 같은 경우로 나눌 수 있다.

1. 검사하는 숫자가 LIS의 마지막 숫자보다 큰 경우

→ LIS에 추가

2. 검사하는 숫자가 LIS의 마지막 숫자보다 작은 경우

→ LIS 내의 적당한 위치를 찾아 갱신

 

문제의 예시보다 더 복잡한 경우인 {10, 20, 30, 15, 25, 50, 40} 수열을 예로 들어보면

맨 처음 LIS 배열에는 {10}이 초기상태로 주어진다.

 

20은 10보다 크므로 LIS는 20을 추가한 {10, 20}이 된다.

마찬가지로 30도 20보다 크므로 LIS는 {10, 20, 30}이 된다.

 

15는 LIS의 가장 큰 값인 30보다 크지 않다.

하지만 위의 LIS의 핵심에 대한 설명처럼 LIS의 길이가 가장 길기 위해서는 상호 원소 간 값의 차이가 작아야 한다.

따라서 기존의 값을 좀 더 작은 값으로 갱신해야 한다.

{10, 20, 30} 중 15를 어떤 값과 갱신해야 할까?

LIS의 원소는 증가해야 되기 때문에 15보다 큰 수 중 가장 차이가 적게 나는 20과 갱신해야 한다.

🤔 원소를 추가하지 않고 갱신하는 이유
만약 seq가 {10, 20, 30, 15}이고 위의 방법대로 LIS값을 구하면 {10, 15, 30}이 되는데 이는 실제 LIS인 {10, 20, 30}과는 다른 값이 나온다. 따라서 LIS를 출력해야 될 경우 이 방법대로 하면 틀린 답이 나온다.
하지만 이 문제에서 구해야 되는 것은 길이이기 때문에 LIS의 원소는 상관이 없고, 최대한 많이 배치할 수 있도록 원소를 갱신해 최대 길이를 구하는 것이다.

만약 seq가  {10, 20, 30, 15, 25, 50, 40} 이어도 LIS가 {10, 15, 25, 50} 이나 {10, 15, 25, 40} 이나 길이에 영향이 없기 때문에 위의 풀이가 가능하다.

 

25도 LIS의 가장 큰 값인 30보다 크지 않기 때문에 상호 원소 간 값 차이가 적게 갱신해야 한다.

따라서 20보다 크면서 가장 차이가 적게 나는 30과 갱신하면 LIS는 {10, 15, 25}이 된다.

 

이처럼 갱신를 할 때 기준 값보다 큰 가장 가까운 원소를 찾을 때 이분 탐색을 사용하게 된다.

이분 탐색은 O(logn)의 시간복잡도를 가지기 때문에 이전 문제에서 사용했던 DP 알고리즘보다 빠르게 값을 구할 수 있다. 

 

[코드]

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
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());
        StringTokenizer st = new StringTokenizer(br.readLine());
        int[] seq = new int[n];
        for (int i = 0; i < n; i++) seq[i] = Integer.parseInt(st.nextToken());

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

            if (LIS.get(LIS.size() - 1) < key) LIS.add(key);
            else {
                int low = 0;
                int high = LIS.size() - 1;
                while (low < high) {
                    int mid = (low + high) / 2;
                    if (LIS.get(mid) >= key) high = mid;
                    else low = mid + 1;
                }
                LIS.set(high, key);
            }
        }
        System.out.println(LIS.size());
    }
}