[백준] 가장 긴 증가하는 부분 수열 2 - JAVA

문제

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

풀이

dp를 통해 답을 구하게 되면 시간 초과가 나오게 된다.
dp로 구할경우 시간 복잡도가 O($n^2$)가 되므로 시간초과가 나오는건 당연하다.. 그러면 어떻게 구해야 할까?? 이는 이분탐색을 이용하여 nlogn의 시간복잡도를 가지게 만들 수 있다.

A = {10, 20, 60, 40, 50, 60} 인경우에 답을 구해보는 과정을 알아보자 LIS는 가장 긴 증가하는 부분 수열의 길이를 알아낼 배열이다.

먼저 초기에는 A[0]값을 넣어준다
LIS = {10}
이제 A의 원소값고 LIS의 가장 마지막의 원소값을 비교하여 A의 원소가 더크다면 LIS배열에 추가해준다.
LIS = {10,20}
LIS = {10,20,60}
여기까지는 문제가 없지만 A의 원소값이 LIS배열의 마지막 원소값보다 작은 경우에는 어떻게 해야할까?? 만약 더해주지 않고 그냥 넘긴다면 LIS의 최종값은 {10,20,60}으로 총길이가 3이 된다. 하지만 답은 {10,20,40,50,60}으로 5가 되어야 한다.

먼저 우리는 가장 마지막 원소값이 A의 원소값보다 작을경우에 LIS배열에 해당원소를 더해주고 있다. 그렇다면 40다음에 나오는 50의 값을 LIS배열에 넣어줄려면 LIS배열의 가장 마지막 원소값은 40이 되어야 한다는 소리이다. 즉 60의 인덱스 위치에 40이 와야한다. 그래야 가장 긴 부분 수열을 구할 수 있기 때문이다.

즉 A의 원소값이 LIS배열의 마지막 원소값보다 작은 경우에는 해당 원소값이 들어갈 인덱스를 찾아 해당 인덱스의 값에 A의 원소값을 넣어주면 된다. 즉 대치해주는 것이다.

대치할 인덱스를 찾기위해 이분탐색을 사용한다. 이분탐색을 사용하는 이유는 먼저 해당 배열이 오름차순으로 정렬되어 있어 이분탐색이 가능하고, logn이라는 시간 복잡도를 가지기 때문에 전체 시간복잡도가 nlogn이 되므로 시간내에 풀이가 가능하기 때문이다.

만약 LIS배열이 {10,20,30}이고 A의 원소값이 15라면 이분탐색을해 대치할 인덱스를 찾는과정은 다음과 같다.
(1)
0 10 -> low
1 20 -> middle
2 30 -> high
LIS[middle] > 15 이므로 high = middle
(2)
0 10 -> low,middle
1 20 -> high
2 30
LIS[middle] < 15 이므로 low = middle + 1
(3)
0 10
1 20 -> low,high
2 30
low >= high 이므로 이분탐색 종료
이때 대치될 인덱스는 low가 되므로 LIS[low]에 A의 원소값을 넣어주면 끝난다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st = new StringTokenizer(br.readLine());
    int N = Integer.parseInt(st.nextToken());
    int[] A = new int[N];
    ArrayList<Integer> LIS = new ArrayList<>();
    st = new StringTokenizer(br.readLine());
    for(int i=0; i<N; i++) {
      A[i] = Integer.parseInt(st.nextToken());
    }
    LIS.add(A[0]);
    for(int i=1; i<N; i++) {
      int key = A[i];
      // LIS의 젤 마지막 원소 값보다 크다면 LIS에 넣어주기
      if(LIS.get(LIS.size() - 1) < A[i]) {
        LIS.add(key);
      }else {
        int low = 0;
        int high = LIS.size();
        while(low < high) {
          int middle = (low+high)/2;
          if(LIS.get(middle) < key) {
            low = middle+1;
          }else {
            high = middle;
          }
        }
        LIS.set(low, key);
      }
    }
    System.out.println(LIS.size());
  }
}