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

문제 설명

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

문제 풀이

• 가장 긴 증가하는 부분 수열 문제는 O(N), O(NLogN) 풀이가 존재하는데
  문제의 n = 1000000이므로 O(NLogN) 풀이 방법 적용이 필요하다.
• O(NLogN) 문제 풀이에 필요한 배열은 다음과 같다

  DP[L] : 길이가 L인 증가하는 부분 수열의 마지막 수중 가장 작은 값 저장

• arr를 탐색하며 arr[i]가 DP[maxInd] 보다 크다면 단순히 DP[++maxInd]에 대입해준다.
• 아닌 경우 이분탐색 (Lower Bound)을 통해 정렬된 DP배열의 위치에 arr[i]값을 치환해준다.

public int lowerBound(int lo, int hi, int t) {
	while(lo < hi) {
    	int mid = (lo + hi) / 2;
        if (DP[mid] < t) lo = mid + 1;
        else hi = mid;
    }
    return hi;

소스 코드 (JAVA)

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

public class Main {
    public static BufferedReader br;
    public static BufferedWriter bw;
    public static int N;
    public static int[] arr;
    //dp[l] 길이가 l인 증가 하는 부분 수열의 마지막 수 중 가장 작은 값 저장
    public static int[] dp;

    //해당 수가 대치할 수 있는 위치 좌표를 출력
    public static int binarySearch(int lo, int hi, int t) {
        while(lo < hi) {
            int mid = (lo + hi) / 2;
            if (dp[mid] < t) lo = mid + 1;
            else hi = mid;
        }
        return hi;
    }

    public static int solve() {
        int maxInd = 0;
        for (int i = 1; i <= N; i++) {
            int num = arr[i];

            //가장 큰 수일 때
            if (dp[maxInd] < num) {
                dp[++maxInd] = num;
            }
            //가장 큰 수가 아닐 때
            else {
                int ind = binarySearch(0, maxInd, arr[i]);
                dp[ind] = arr[i];
            }
        }
        return maxInd;
    }

    public static void input() throws IOException {
        N = Integer.parseInt(br.readLine());
        arr = new int[N+1];
        dp = new int[N+1];
        Arrays.fill(dp, -1);
        dp[0] = 0;
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        for (int i = 1; i <= N; i++)
            arr[i] = Integer.parseInt(st.nextToken());
    }

    public static void main(String[] args) throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        bw = new BufferedWriter(new OutputStreamWriter(System.out));
        input();
        bw.write(solve() + "\n");
        bw.flush();
        bw.close();
        bw.close();
    }
}