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

문제

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

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

풀이

해설

LIS

LIS의 구현 문제로 문제의 이름과 같이 가장 긴 증가하는 부분 수열의 길이를 출력하는 문제이다.

DP로 구현한 LIS로도 문제에 대한 결과 값은 출력이 가능하지만, 이 문제의 입력의 크기는 0~1,000,000이다. DP로 LIS를 구현했을 때 시간 복잡도는 O(N^2)이기 때문에 시간초과로 통과할 수 없다.

 

따라서 이 문제는 이분 탐색을 통해 구현한 LIS를 사용해야 한다.

이분 탐색을 사용한 구현

이분 탐색을 이용한 구현은 O(NlogN)의 시간복잡도를 갖기 때문에 통과가 가능하다.

 

그렇다면 어떻게 구현해야할까?

 

LIS를 담아둘 하나의 배열을 생성하고, 수열의 요소들을 돌며 비교한다. 요소가 LIS의 마지막 값보다 크다면 다음 인덱스 값에 요소를 추가하고, 그게 아니라면 이분 탐색을 통해 LIS 배열의 위치에 대체한다.

 

좀 더 구체적으로 알아보도록 하자.

 

if (LIS[lisIndex] < arr[i]) {
    LIS[++lisIndex] = arr[i];
} else {
    int lowIdx = lower_bound(LIS, lisIndex, arr[i]);

    LIS[lowIdx] = arr[i];
}

 

만약 요소(arr[i])가 LIS의 마지막 값(LIS[lisIndex])보다 크다면 다음 요소에 저장한다. 이렇게 되면 요소를 다 돌때까지 증가하는 수열을 만들어낼 수 있다. 하지만 이것으론 가장 길다는 것을 보장하지 못한다. 왜냐면 수열의 요소 값이 LIS[lisIndex] 보다는 작을지 몰라도 그 이전 인덱스 안의 요소들보다 클 수 있기 때문이다.

 

이 문제를 보완하기 위해 가장 시간복잡도의 효율이 좋은 이분 탐색을 이용해 해당 인덱스를 찾아 값을 대체해주는 것이다.

 

private static int lower_bound(int[] lis, int lisIndex, int val) {

int start = 0, end = lisIndex;

while (start < end) {

    int mid = (start + end) / 2;

    if (lis[mid] < val) {
        start = mid + 1;
    } else {
        end = mid;
    }
}

return start;

 

위의 함수는 찾는 값보다 큰 요소의 다음 인덱스를 반환한다. 이것이 의미하는 것은 긴 수열을 만들 수 있는 더 낮은 값으로 대체하는 것이다.

 

예를들어 {1, 2, 5, 8}에서 4라는 값이 val로 들어온다면 5가 4로 대체되어 {1, 2, 4, 8}이 될 것이다. 그리고 이후에 다시 5가 들어와도 {1, 2, 4, 5}가 되고, 이렇게 채워나가다 보면 가장 긴 증가하는 수열이라는 것을 보장할 수 있다.

 

코드

package 가장긴증가하는부분수열2;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
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[] arr = new int[n];
        int[] LIS = new int[n];

        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

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

            if (LIS[lisIndex] < arr[i]) {
                LIS[++lisIndex] = arr[i];
            } else {
                int lowIdx = lower_bound(LIS, lisIndex, arr[i]);

                LIS[lowIdx] = arr[i];
            }
        }

        System.out.println(++lisIndex);
    }

    private static int lower_bound(int[] lis, int lisIndex, int val) {

        int start = 0, end = lisIndex;

        while (start < end) {

            int mid = (start + end) / 2;

            if (lis[mid] < val) {
                start = mid + 1;
            } else {
                end = mid;
            }
        }

        return start;
    }
}