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

문제 바로가기 : https://www.acmicpc.net/problem/12015

메모리 : 96160KB

시간 : 564ms

언어 : Java 11

---

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;
import java.util.StringTokenizer;

public class Main {
    static int[] arr, vector;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        int N = Integer.parseInt(br.readLine());
        arr = new int[N];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
        vector = new int[N];
        vector[0] = arr[0];
        int end = 0;
        for (int i = 0; i < N; i++) {
            if (vector[end] < arr[i]) {
                vector[++end] = arr[i];
            } else {
                int reidx = replace(arr[i], 0, end);
                vector[reidx] = arr[i];
            }
        }
        System.out.println(end + 1);
    }

    private static int replace(int num, int left, int right) {
        while (left < right) {
            int mid = (left + right) / 2;
            if (vector[mid] < num) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return right;
    }
}

해설

가장 긴 증가하는 부분수열(LIS)는 DP로도 해결이 가능한 문제지만, 수열의 크기가 큰 경우 O(N^2)로 시간초과가 발생하게된다! 따라서 O(N logN)으로 풀 수 있는 방법을 사용해야한다. 이 또한 메모이제이션인데 탐색하는 부분을 이분탐색을 이용해 logN으로 구현이 가능하다.

//수열을 저장할 배열
 vector = new int[N];
 //맨 처음은 언제나 가장 길지
 vector[0] = arr[0];
 //맨 마지막 idx
 int end = 0;
 //arr배열을 돌면서 가장 긴 증가하는 부분수열을 찾아본다.
 for (int i = 0; i < N; i++) {
    //맨 마지막 수는 가장 커야한다. 지금의 가장 큰 수 보다 arr[i]가 더 크면 이어붙이기
    if (vector[end] < arr[i]) {
        vector[++end] = arr[i];
    } else {
        //작으면 이분탐색으로 맞는 위치 찾아서 바꾸기
        int reidx = replace(arr[i], 0, end);
        vector[reidx] = arr[i];
    }
 }