[JAVA] 백준 가장 긴 증가하는 부분 수열 2_이분탐색

 

문제 : 

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

 

 

 

접근 : 

 

  - 빈 증가하는 부분 수열 (res) 리스트를 만든다.

 

  - 입력값이 들어오면 증가하는 부분수열(res)을 2진 탐색 하여 집어 넣을 idx를 찾아낸다.

 

  - 만약, 입력값과 동일한 값이 있으면 그 idx를 출력한다.

 

  - 만약 입력값이 res 의 크기보다 큰경우 res에 가장 뒤에 추가해준다.

 

  - 만약 입력값의 집어넣을 위치에 이미 다른 값이 있으면 둘 중 더 작은값으로 갱신한다.

 

  - 입력 끝까지 위의 과정을 반복한 후 증가하는 부분수열(res)의 크기를 출력한다.

 

 

 

 

코드 구현 :

 

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

public class Main {

    private static int findInsertPosition(int num, ArrayList<Integer> res) {
        int left = 0, right = res.size() - 1;

        while (left <= right) {
            int mid = (left + right) / 2;

            if(res.get(mid) == num) return mid;

            if (res.get(mid) > num) {
                right = mid - 1;
                continue;
            }
            left = mid + 1;
        }
        return left;
    }

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

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        ArrayList<Integer> res = new ArrayList<>();

        for(int i = 0 ; i < n ;i++){
            int now_value = Integer.parseInt(st.nextToken());
            int insertPosition = findInsertPosition(now_value, res);

            if (insertPosition == res.size()) res.add(now_value);
            else if (res.get(insertPosition) > now_value) res.set(insertPosition, now_value);
        }

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