백준 12015 가장 긴 증가하는 부분 수열 2 (Java)

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

 

1. 문제

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.

예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.

입력

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다.

둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000)

출력

첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다.

2. 풀이

기존에 사용하던 LIS 코드는 다음과 같다.

for(int i=1;i<n;i++){
    for(int j=0;j<i;j++){
        if(arr[j]<arr[i]){
            dp[i]=Math.max(dp[i], dp[j]+1);
        }
    }
}

 

이렇게 구현하면 시간복잡도는 O(n^2)가 된다. 그러나 수열의 크기는 10^6이므로 최대 크기로 구현하게 되면 1초 기준으로 시간초과가 발생한다. 더 빠른 알고리즘을 사용해야 한다.

 

O(nlogn)의 알고리즘을 사용해보자.  A = {10, 20, 15, 30, 25, 50}를 사용할 것이다.

10

 

우선 가장 처음에 있는 숫자를 넣는다.

10

20

다음 숫자는 LIS의 마지막 숫자보다 크므로 그대로 집어넣어 준다.

15

20

다음은 15이다. 어짜피 LIS의 가장 큰 수는 20으로 고정이므로 15부터 시작하는 LIS를 새로 하나 만들어 배열에 겹친다. 즉, {10, 20}과 {15}를 겹치는 데, 이렇게 하더라도 LIS의 길이는 변하지 않는다.

15

20

30

다음은 30이다. 현재는 {10, 20, 30}과 {15}가 겹쳐있는 상태이고, 이에 따라 LIS의 길이는 3이다.

15

25

30

다음은 25이다. {10, 20, 30}, {15, 25}가 겹쳐있고, LIS의 최댓값은 30, 최장 길이는 25이다.

15

25

30

50

마지막 숫자까지 넣어서 LIS를 구하였다. 길이는 4이다.

 

이를 구현하면 다음과 같다.

        for (int i = 1; i < n; i++) {

            if (dp[ans - 1] < arr[i]) {
                ans++;
                dp[ans - 1] = arr[i];
            } else {

                int s = 0;
                int e = ans;

                while (s < e) {
                    int mid = (s + e) / 2;

                    if (dp[mid] < arr[i]) {
                        s = mid + 1;
                    } else {
                        e = mid;
                    }
                }

                dp[s] = arr[i];
            }

        }

 LIS에 최댓값을 넣어야 하면 맨 뒤에 집어넣는다. 그렇지 않다면 이전까지 만든 LIS에 들어갈 자리를 찾아서 덮어씌운다.

연산이 끝나고 dp의 크기를 출력하면 정답을 구할 수 있다.

3. 코드 전문

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class Main {

    static int n;

    static int[] arr;

    static int ans = 1;

    static int[] dp;



    public static void main(String[] args) throws IOException {

        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer tokenizer;

        n = Integer.parseInt(reader.readLine());

        arr = new int[n];
        dp = new int[n];


        tokenizer = new StringTokenizer(reader.readLine());
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(tokenizer.nextToken());
        }

        dp[0] = arr[0];

        for (int i = 1; i < n; i++) {

            if (dp[ans - 1] < arr[i]) {
                ans++;
                dp[ans - 1] = arr[i];
            } else {

                int s = 0;
                int e = ans;

                while (s < e) {
                    int mid = (s + e) / 2;

                    if (dp[mid] < arr[i]) {
                        s = mid + 1;
                    } else {
                        e = mid;
                    }
                }

                dp[s] = arr[i];
            }

        }





        System.out.println(ans);

    }
}