Binary Search: 백준 가장 긴 증가하는 부분 수열 2 - 12015

문제 유형

Binary Search

작성 코드

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;


public class Main {
    public static int N;
    public static long[] given;
    public static List<Long> dynamic;

    public static int getIndex(long num) {
        int right = dynamic.size() - 1;
        int left = 0;
        int center;
        while (left <= right) {
            center = (left + right) / 2;
            if (dynamic.get(center) >= num) {
                right = center - 1;
            } else {
                left = center + 1;
            }
        }
        return left;
    }

    public static void pro() {
        for (long num: given) {
            int index = getIndex(num);
            if (index  == dynamic.size()) dynamic.add(num);
            else dynamic.set(index, num);
        }

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

    public static void input() {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        given = new long[N];
        dynamic = new ArrayList<>();
        for (int i = 0; i < N; i++) {
            given[i] = sc.nextLong();
        }
    }

    public static void main(String[] args) {
        input();
        pro();
    }
}

 

접근방식

예시)

5
10 20 10 30 20 50

 

1. 주어진 수열에서 상승하는 부분 수열이라고 했으니 먼저 부분수열을 찾으려고 했다.

2. 10 20 30 50이 정답이고 여기서 아래와 같은 패턴을 찾게 됐다.

0 <- 10

10 <- 20

10 20 <-10

10 20 <- 30

10 20 30 <- 20

10 20 30 <- 50

10 20 30 50 (정답)

 

여기서와 같이 작을 경우 같을 경우 큰수일경우가 갈리게 되는데 새로 들어온 숫자가 같거나 작을경우에 늘어나는 수열에서의 정확한 위치만 찾아주면 된다. 

 

이를 위해서 이분탐색을 사용하여 탐색 시간을 낮추었다. 여기서 중요한점은 이분탐색을 사용할 경우 가장큰 수일경우 left가 가장 오른쪽 끝으로 간다는 사실을 알게 됐다.

 

그래서 이분탐색으로 새로 들어온 숫자가 들어가야하는 위치를 파악하고 그 위치가 만약 dynamic 수열의 길이와 같다면 추가했다.