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

12015번: 가장 긴 증가하는 부분 수열 2 (acmicpc.net)

12015번: 가장 긴 증가하는 부분 수열 2

어떻게 생각하고 문제를 풀었는가?

주어진 수열에서 부분 수열의 원소들이 인덱스가 증가함에 따라 값도 증가함을 만족한다면 증가하는 부분 수열이 될 수 있습니다.

첫번째 인덱스부터 탐색을 시작하여 부분 수열을 형성하고, 마지막 원소보다 작은 값이 발견되었을 경우 부분 수열을 새로 형성하거나, 해당 원소를 무시하고 다음 원소를 탐색하여 부분 수열에 추가함으로써 가장 긴 증가하는 부분 수열을 찾을 수 있습니다.

결과적으로 반환해야 하는 것은 부분 수열의 최대 길이이므로 부분 수열의 원소를 작은 값으로 갱신함으로써 길이만을 보존하고 답을 찾을 수 있을 것이라고 생각하였습니다.

코드

import java.io.*;
import java.util.ArrayList;
import java.util.StringTokenizer;

class Main {
    private static final ArrayList<Integer> sequence = new ArrayList<>();

    public static void main(String[] args) throws IOException {
        readInput();
        System.out.println(sequence.size()-1);
    }

    private static void readInput() throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(reader.readLine());
        StringTokenizer tokenizer = new StringTokenizer(reader.readLine());
        sequence.add(0);
        for(int i=0; i<n; i++){
            int num = Integer.parseInt(tokenizer.nextToken());
            if(num > sequence.get(sequence.size()-1)){
                sequence.add(num);
            }else{
                int index = lowerBound(num);
                sequence.set(index, num);
            }
        }
        reader.close();
    }

    private static int lowerBound(int target){
        int left = 1;
        int right = sequence.size()-1;
        int result = 0;
        while(left < right){
            int mid = (left+right)/2;
            if(sequence.get(mid) >= target){
                result = mid;
                right = mid-1;
            }else{
                left = mid+1;
            }
        }
        return result;
    }

}

이분 탐색을 사용하여 부분 수열의 최대 길이를 찾는 코드를 작성하였습니다.

O(n)의 탐색으로는 최대 1,000,000 크기의 수열로부터 부분 수열을 찾을 수 없기 때문에 이분탐색을 이용하여 O(nlogn)으로 탐색 시간을 줄일 수 있습니다.

각 인덱스를 탐색하여 부분 수열에 원소를 추가하고, 추가하려는 원소가 부분 수열의 마지막 값보다 작은 값을 갖는 경우 해당 값보다 작거나 같은 가장 큰 원소를 이분 탐색으로 찾고, 해당 원소와 바꾸도록 함으로써 새로운 부분 수열을 형성합니다.

이후 마지막 원소보다 큰 값을 갖는 원소가 추가될 경우 부분 수열에 추가됨으로써 기존 부분 수열의 최대 길이를 찾을 수 있습니다.