백준 12015 가장 긴 증가하는 부분 수열 2 Java [LIS]

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

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

N이 1000000까지니까 NlogN 안으로 풀어야한다

 

예제

A 10 20 10 30 20 50

D  1   2   1   3   2   4

예제는 중복되는 숫자가 있어서 규칙을 찾기가 힘들다

 

예제 2

A 11 20 10 30 19 50

D  1   2   1   3   2   4

거리배열을 만들어서 배열 가장 끝값보다 크면 배열에 추가해준다

배열보다 작으면 이진탐색으로 작은값 중에 가장 큰값 찾아서 그 다음 인덱스 값과 교체해준다

 

import java.io.*;
import java.util.*;

public class Main {
    static ArrayList<Integer> arrayList;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int[] arr = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        arrayList = new ArrayList<>();
        arrayList.add(0);
        for (int n = 0; n < N; n++) {
            if (arrayList.get(arrayList.size()-1) < arr[n]) {
                arrayList.add(arr[n]);
                continue;
            }
            binarySearch(arr[n]);
        }
        System.out.println(arrayList.size()-1);
    }

    static void binarySearch(int num) {
        int l = 0, r = arrayList.size()-1;
        while (l < r) {
            if (l+1 == r) {
                arrayList.set(r, num);
                break;
            }
            int m = (l + r) / 2;
            if (num > arrayList.get(m)) {
                l = m;
            } else {
                r = m;
            }
        }
    }
}

 

찾아보니 Arrays의 메서드에 이진탐색이 있다...

이진탐색에 오버로딩된 메서드에 (배열, to index, from index, key) 값으로 찾을 수 있는게 있다

이 메서드를 사용하면 ArrayList를 사용하지않고 배열을 사용하여 훨씬 쉽고 빠르게 해결할 수 있다!!

이진 탐색 메서드를 사용해서 풀이한 유사 문제(입력값 조건만 다름) 코드

https://jjong2.tistory.com/32

백준 12738 가장 긴 증가하는 부분 수열 3 Java