[PS] BOJ12738 가장 긴 증가하는 부분 수열3 ( LIS ) with JAVA

 

12738번: 가장 긴 증가하는 부분 수열 3

 

 

◎ 문제 풀이

 

[PS] BOJ12015 가장 긴 증가하는 부분수열2 ( LIS ) with JAVA

(위 문제와 풀이는 똑같다.  풀이에 대한 핵심은 위 포스팅을 참고하기를 바란다.  )

 

 

이분탐색이 어려운 이유는 문제에 따라 어느 탐색구간에 mid를 포함해야 하는지 판단이 필요하기 때문이다.

어떤 의미인지 그림으로 알아보자. 

 

 

 

 

 

LIS 수열에 37을 넣으려고 한다.

 

0과 3 사이의 mid는 1이다. 인덱스 1이 가리키는 값은 20이다.

 

20은 37보다 작다.

 

LIS는 증가하는 수열이므로

인덱스2 (mid+1)와 인덱스 3(end) 사이에서 다음 이분탐색을 해야한다. 

 

 

그럼 위 LIS를 보자. 

 

0과 3 사이의 mid는 1이다. 인덱스 1이 가리키는 값은 40이다.

 

40은 37보다 크다. 

 

LIS는 증가하는 수열이므로

인덱스0(start)와 인덱스1(mid) 사이에서 다음 이분탐색을 진행해야 한다. 

 

 

정리하면 

 

mid값 < 37 이면 mid+1 ~ end 구간을 탐색하고

mid값 > 37 이면 start ~ mid 구간을 탐색한다. 

 

그 이유는 LIS는 최대한 촘촘해야 하기 때문이다. 촘촘의 의미는 위에 공유한 포스팅에 정리되어 있으니 참고 바란다. LIS는 수와 수 사이가 작은 쪽으로 촘촘해야 최장으로 증가하는 수열이 된다. 

 

10 40 50 70 보다 10 37 50 70이 LIS에 가깝다. 그러므로 mid값이 37보다 크면 mid값이 37로 대체가 가능하도록 start-mid 구간을 탐색해야 한다. 반대로 mid값이 37보다 작은데 mid값이 37을 대체하면 수와 수 간격이 넓어진다. 10 20 40 50 이 10 37 40 50 이 되면 수와 수사이가 넓어진다.

 

그러므로 최대한 작은쪽으로 수와 수 사이의 간격을 촘촘히 만들려면 

 

mid값 < 37 이면 mid+1 ~ end 구간을 탐색하고

mid값 > 37 이면 start ~ mid 구간을 탐색해야 한다. 

 

이처럼 문제가 요구하는 바에 따라 mid가 어느 탐색구간 포함되어야 하는지가 달라지므로 주의해서 이분탐색을 구현해야 한다. 

 

◎ 코드

//BOJ12738 가장 긴 증가하는 부분 수열3
public class Main {

    static List<Integer> lis;
    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());
        int[] arr = new int[n];
        lis = new ArrayList<>();

        StringTokenizer st = new StringTokenizer(br.readLine());

        for(int i=0;i<n;i++){
            arr[i] = Integer.parseInt(st.nextToken());
        }

        lis.add(arr[0]);

        for(int i=1;i<n;i++){

            int last = lis.get(lis.size()-1);

            if( last < arr[i] ) lis.add(arr[i]);
            else {
                int index = binarySearch(0, lis.size() - 1, arr[i]);
                lis.set(index,arr[i]);
            }
        }

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

    public static int binarySearch(int start, int end, int value){
        if( start == end ) return end;

        int mid = ( start + end )/2;

        if( lis.get(mid) >= value ) return binarySearch(start,mid,value);
        else return binarySearch(mid+1,end,value);
    }

}