백준 12015 ( Java )

가장 긴 증가하는 부분 수열 2

 

가장 긴 증가하는 부분 수열을 구하는 문제이다. 

 

 

문제 풀이

 

가장 긴 증가하는 부분 수열을 직접 만든 뒤, 길이를 출력하면 된다. 그러면 가장 긴 증가하는 부분 수열은 어떻게 만들까?

 

수열 A의 첫 번째 원소부터 마지막 원소까지 참조해가면서 참조한 원소가 만들고 있던 부분 수열의 마지막 원소보다 크다면 부분 수열의 꼬리에 추가, 작거나 같다면 부분 수열에서 알맞은 위치에 덮어쓰면 된다. 여기서 알맞은 위치를 찾는데 이분 탐색 알고리즘을 적용한다.

 

 

import java.util.Scanner;
import java.util.ArrayList;
 
public class Main {
 
    public static void main(String [] args) {
 
        Scanner sc = new Scanner(System.in);
 
        int N = sc.nextInt();
 
        ArrayList<Integer> arr = new ArrayList<>();
 
        arr.add(0);
 
        for (int i = 0 ; i < N ; i++) {
 
            int temp = sc.nextInt();
 
            if (arr.get(arr.size() - 1) < temp) {
                arr.add(temp);
            }
            else {
                int left = 1;
                int 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);
    }
}
 

 

 

 

결과