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

in Algorithm on 기타

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

풀이

가장 긴 증가하는 부분수열(LIS)의 길이를 구해야 한다.

dp로 풀어보았으나 시간초과가 났다.

dp로 푸는 풀이는 N^2의 시간복잡도를 갖는다.

이분 탐색으로 푸는 방법을 채택하여 NlogN으로 시간을 줄였다.

배열을 만들어 숫자가 들어갈 위치를 찾아 그 숫자를 배열에 넣는다.

배열의 마지막 값보다 숫자가 크다면 그 다음 칸에 숫자를 넣고,

작다면 이분탐색을 통해 들어갈 위치를 찾아 갱신해 주면 되는 문제였다.

메모리: 95952KB

시간: 528ms

언어: Java 11

코드

import java.io.*;
import java.util.*;

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());
        int[] arr = new int[N];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        int[] dp = new int[N + 1];
        int max = 0;
        for (int i = 0; i < N; i++) {
            if (arr[i] > dp[max]) {
                dp[++max] = arr[i];
            } else {
                int idx = binarySearch(dp, 0, max, arr[i]);
                dp[idx] = arr[i];
            }
        }

        System.out.println(max);
    }

    private static int binarySearch(int[] arr, int left, int right, int key) {
        int mid = 0;
        while (left < right) {
            mid = (left + right) / 2;
            if (arr[mid] < key) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }

        return right;
    }

}