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

made by : besforyou

 

 

문제 풀이

 

수열의 크기가 1 <= N <= 1,000,000 이므로 시간복잡도가 N^2 이상인 알고리즘은 사용할 수가 없다.

그러므로 이분 탐색을 활용하여 가장 긴 증가하는 부분 수열을 직접 만들자.

 

1. 수열을 읽어들이면서 부분수열의 마지막 원소와 비교한다.
2. 마지막 원소보다 큰 원소는 바로 정답 배열 마지막에 추가
3. 그렇지 않은 원소는 부분수열에 적절한 위치에 배치한다.
4. 생성한 가장 긴 증가하는 부분 수열의 길이를 반환

 

코드

 

import java.io.*;
import java.util.ArrayList;
import java.util.StringTokenizer;
 
public class Main {
    static int N;
    public static void main(String [] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        ArrayList<Integer> arr = new ArrayList<>();
        arr.add(0);
        for (int i = 0 ; i < N ; i++) {
            int temp = Integer.parseInt(st.nextToken());
            if (arr.get(arr.size() - 1) < temp) {
                arr.add(temp);
            } else {
                int left = 1, right = arr.size() - 1;
                while (left < right) {
                    int mid = (left + right) / 2;
                    if (arr.get(mid) < temp) {
                        left = mid + 1;
                    } else
                        right = mid;
               }
                arr.set(right, temp);
            }
        }
        System.out.print(arr.size() - 1);
    }
}