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

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

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

---

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int[] A = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        List<Integer> LIS = new ArrayList<>();
        int lastIdx = 0;
        LIS.add(A[0]);
        for (int i = 1; i < N; i++) {
            int num = A[i];
            if(LIS.get(lastIdx) < num){
                lastIdx++;
                LIS.add(num);
                continue;
            }
            //자리 바꿀 수 찾기 위해 이분탐색
            int low = 0, high = lastIdx + 1;
            while (low < high){
                int mid = (low + high) / 2;
                if (LIS.get(mid) < num) {
                    low = mid + 1;
                } else {
                    high = mid;
                }
            }
            LIS.set(low, num); //대체
        }
        //길이 == 마지막 인덱스 +1
        System.out.println(LIS.size());
    }
}

💡 이진탐색

풀이

https://c-omealong.tistory.com/100

[JAVA] 백준 11053번 : 가장 긴 증가하는 부분 수열

위 문제와 유사함. but!! A[i] 원소 범위가 10^6이므로 dp를 사용하기엔 어렵다. (이중 for문 이므로)

이때 사용하는 것이 바로 binary search이다.

1. A[0] -> LIS 배열에 원소를 넣어준다.

2. A[1 ~ ] -> LIS의 마지막 숫자보다 크다면 LIS 배열 뒤에 넣어준다.

                 혹은 LIS보다 작다면, LIS 배열에서 A[i]보다 크면서, 그 차이가 가장 작은 원소를 replace한다.

대체 하는 이유 : 문제에서 원하는 것은 결국 길이. 즉, 추가하는게 아닌 대치를 해야 길이를 유지하며 이어나갈 수 있음
 e.g. {10, 20, 30, 15}의 경우 - {10, 20, 30} - {10, 15, 30} / {10, 15, 20, 30} 삽입하면 길이가 바뀌므로 대치해야 함 (대치한 자리 뒤는 어차피 다음 수들 들어오며 마찬가지로 대체될 예정이라 괜찮다~)

 

즉 알고리즘의 흐름은 이렇다

• LIS 배열을 별도로 선언해준다. 처음 값은 A[0]의 값으로 할당해준다.
• 1부터 진행하며 LIS의 마지막 값(LIS[last])과 대소를 비교한다 >>> 이분 탐색으로 진행
  • A[i] > LIS[last] : LIS[last + 1]에 추가해준다
  • A[i] < LIS[last] : LIS 원소 중 A[i]보다 크면서, 차이가 가장 작은 원소를 replace한다
    • 이때 해당 조건을 만족하는 원소를 찾기 위해 이분 탐색을 진행한다
• 마지막 길이를 구할 때 배열을 사용할 경우 lastIdx를 관리하기 까다로워서,,, ArrayList를 사용했다
  • 이분 탐색의 원리를 잘 알고 구현해야한다.. low = mid+1로 해야 num보다 크면서 가까운 수 구할 수 있음