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

문제 링크 : https://www.acmicpc.net/problem/12015

이 문제는 이분 탐색을 이용하여 풀 수 있습니다.

가장 긴 증가하는 부분 수열을 구하는 방식은 다음과 같습니다.

1. 수열 A를 탐색하면서 가장 긴 증가하는 부분 수열이 비었을 경우 수열 A 값을 추가
2. 부분 수열이 비어있지 않은 경우 가장 밖에 있는(가장 큰) 수가 수열 A보다 작을 경우 A 값을 추가
3. 가장 큰 수가 수열 A보다 클 경우 부분 수열 내의 수 중 수열 A보다 큰 수 중 가장 작은 수와 대치

이 때 3번의 경우 문제에서 구하고자 하는 것이 수열의 길이이기 때문에 대치하는 방식으로 진행하여도 길이 자체는 변화가 없으며, 뒤의 다른 큰 수가 왔을 때 추가 작업이 용이하기 때문에 대치로 진행합니다.

이 과정에서 부분 수열 내의 수 중 수열 A보다 큰 수 중 가장 작은 수의 탐색을 이분 탐색으로 진행합니다. 0과 수열의 최대 인덱스를 양 끝 범위로 하여 중간값 인덱스가 현재 값보다 크거나 같을 경우 현재 인덱스를 최댓값으로, 그렇지 않다면 최소 인덱스를 증가시키는 방식으로 구합니다.

다음은 코드입니다.

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

class Main{
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        int[] A = new int[N];
        for(int i=0;i<N;i++) A[i] = Integer.parseInt(st.nextToken());

        List<Integer> res = new ArrayList<>();
        for(int i=0;i<N;i++){
            int val = A[i];
            if(res.isEmpty()) res.add(val);
            else{
                if(res.get(res.size()-1) < val) res.add(val);
                else{
                    int min = 0;
                    int max = res.size()-1;
                    while(min<max){
                        int mid = (min+max)/2;
                        if(res.get(mid)>=val) max=mid;
                        else min=mid+1;
                    }
                    res.set(max,val);
                }
            }
        }

        System.out.println(res.size());
    }
}