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

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

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

문제 풀이

https://www.acmicpc.net/problem/11053을 확인해보면 같은 LIS를 구하지만 탐색 범위에서 차이가 난다. 기존 dp를 활용하는 이 예제에서는 현재 인덱스의 LIS를 구하기 위해 이전 dp를 조회했어야 한다. 하지만 이 문제는 범위가 100배 늘어나 더욱 효율적인 코드가 필요하고 따라서 이분탐색을 통해 LIS를 구해야 한다.

 

분명 이분탐색 알고리즘이 들어가긴 하지만 문제를 풀기 위한 접근 방법은 새로운 패러다임인 것 같다.

https://st-lab.tistory.com/280 이 링크를 참고했다.

 

먼저 우리가 구하는 LIS를 구하기 위해서 새로운 접근법을 시도한다. LIS란 가장 긴 증가하는 부분 수열로 가장 길기 위해 어떻게 접근해야 할까?

 

'LIS의 요소가 갖는 값의 범위가 클 수록 부분 수열에 넣어줄 수 있는 범위가 많아진다' 즉 LIS 20,30이 가질 수 있는 경우의 수 보다 15, 30에 대해 더 많은 숫자를 추가해줄 수 있다는 뜻이다. 따라서 20,30 다음에 15가 나왔다면 15,30으로 바꿔준다. 바꿔주면 LIS 길이의 영향을 주는 것 아닌가?하고 생각할 수 있지만 보았듯이 20,30 -> 2개 / 15,20 -> 2개로 길이에는 영향을 주지 않는다. 단지 가장 긴 부분 수열을 구하기 위한 범위 설정이라고 이해하면 될 것 같다.

 

물론 30보다 큰 수에 대해서는 맨 뒤에 추가만 해주면 된다. 이때는 LIS의 길이가 1 증가한 것이라고 이해하면 된다.

 

위 내용을 코드로 구현해보자.

 

코드

package 백준;

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

public class b12015 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[] nums = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        int[] LIS = new int[n];

        // 첫 번째 값을 넣어 두고 시작
        LIS[0] = nums[0];
        int len = 1;

        for (int i = 1; i < n; i++) {
            // lis의 마지막 값보다 nums의 값이 더 크다면 lis 마지막에 추가
            if (LIS[len - 1] < nums[i]) {
                LIS[len] = nums[i];
                len++;
            }
            // nums보다 큰 값 중 가장 왼쪽을 찾아 교체
            else {
                int left = 0;
                int right = len;
                int findNum = nums[i];

                // under bound 이분 탐색 진행,
                while (left < right) {
                    int mid = (left + right) / 2;

                    if (findNum > LIS[mid]) {
                        left = mid + 1;
                    } else {
                        right = mid;
                    }
                }
                LIS[left] = findNum;
            }
        }

        System.out.println(len);

    }
}

느낀점