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

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

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

 

1. 문제의 유형 및 이해

이분탐색

유명한 LIS(Longest Increasing Subsequence) 알고리즘 입니다.

주어진 수열에서 가장 긴 증가하는 부분 수열을 찾으면 됩니다.

알려진 방법으로 LIS알고리즘을 푸는 방법은 크게 3가지

dp, 이분탐색, segment tree가 있습니다. 

dp의 경우 O($N^2$) 으로 N의 범위가 커진다면 해결하는데 어려움이 있습니다.

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

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

의 경우 N의 범위가 1~1000으로 O($N^2$)으로 가능하지만 이번 문제의 경우 불가능합니다.

우리는 이분탐색을 활용하여 NlogN 시간복잡도로 풀어낼 수 있습니다.

2. 문제 접근 방법

문제에서 원하는 정답은 '가장 긴 증가하는 부분 수열의 길이' 입니다.

결국 1 2 5 10 9 와 같은 수열이 있을 때 LIS는 1 2 5 10 또는 1 2 5 9 이지만, 우리가 원하는 정답은 4로 동일합니다.

실제로 증가하는 부분 수열을 출력하는 문제는 ' 가장 긴 증가하는 부분수열 시리즈'를 통해 경험할 수 있습니다.

 

돌아와서, 우리는 부분 수열이 더 늘어날 수 있는지에 집중하면 됩니다.

어떤 배열 하나를 두고 여기에다가 부분 수열을 기록하는 겁니다.

예시에서의 11 20 10 30 21 50를 보도록 하면

1 : [11]  length 1

2 : [11, 20]  length 2 // 가장 증가했을 때 수가 1이였기 때문에 그 값보다 크다면 부분 수열을 증가 시켜 줍니다.

3 : [10,20] length 2 //  뒤에서 설명

4 : [10, 20, 30] length 3

5 : [10, 20, 21] length 3

6 : [10, 20, 21, 50] legnth 4

3번째와 5번째를 통해 원리를 이해할 수 있습니다.

3번째 경우에서 11 20 10 이 들어왔을 때 가장 긴 증가하는 부분 수열은 11 20이 됩니다. 이미 길이는 측정이 된 상태이죠. 이후에 변하는 [10, 20]은 실제 가장 긴 증가하는 부분 수열이 아닌, 10이 만약에 부분수열로써 참여하게 된다면, 어디서 시작할 수 있는가를 의미하는 것이 조금 더 가깝습니다. 

 

'만약에 부분 수열로써 참여하게 된다면'이라는 말이 조금 헷갈릴 수 있는데, 다음과 같이 생각해봅시다.

이후에 만약 11 20 10 11 12 13이 들어온다면 이를 처리하기 위해 10의 위치는 어디로 가야할지를 정하는 것과 같습니다. 가장 긴 증가하는 부분 수열에 영향을 끼치지도 않았고, 이후에 들어올 값들에 대해서 고려할 수 있습니다.

 

즉, 이분탐색을 이용하는 방법은 어떠한 x가 실제 부분 수열에 참여하게 될 경우 어디에 위치할 수 있는가를 찾기위해서 이분탐색으로 빠르게 자신의 자리를 찾는데 의의가 있습니다.

 

이어서 5번 경우를 보게되면 21이 들어왔을 때 20보다는 크고 30보다는 작은 위치에 있습니다.

이전에 들어온 값들이 항상 자신보다 이전에 위치하고 있기 때문에 자신보다 큰 친구를 갈아끼워주면 자신의 위치로써 활동할 수 있는 것입니다.

 

정리하자면, '새로운 부분수열로써 참여할 가능성이 있는 위치에 기록한다' 이라는 말에서 조금 바꾸어 보면

매 탐색마다 마지막 값중 최솟값 을 통해 새로운 부분수열을 확인할 수 있다. 라는 것입니다.

새로운 부분 수열의 [min ~~~ max]값을 갱신해주는 것이죠.

9 5 10 이라면 9 10이나 5 10 이나 동일하기 때문에 5와 9의 자리가 동일하고, 이후에 7 , 8 이 들어왔을 때 

그 전 최소 값인 5로 시작하는 것이 더 길고 새로운 LIS를 보장합니다.

또한 9 5 10 9 라고할 때

[min 5 ~ max 10]에서 [min 5 ~ max 9]로 갱신해주면서 길이는 변하지 않고 새로운 부분수열에서 더 많은 값들을 확인할 수 있습니다. 실제로 그 값이 수열이 아닐지라도 그 전 수열 값들은 내포하고 있기 때문에 길이를 구한다는 면에서는 정답이 변하지 않습니다. 

 

예시)

15 9 11 8 10 12 7 6

15

9

9 11

8 11  (8은 9를 내포하고 있다고 생각해도 무방)

8 10 (10은 11을 내포하고 있다고 생각해도 무방)

8 10 12

7 10 12

6 10 12 (실제 증가하는 부분 수열은 아니지만 마지막 min값이 6인 부분수열과 지금까지 갱신한 모든 길이가 3인 부분 수열도 내포하고 있습니다)

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

/**
 * @문제번호 : Q12015
 * @문제이름 : 가장 긴 증가하는 부분 수열 2
 * @난이도 : Gold II
 * @date :  2022-02-15 오후 1:36
 * @author : pcrmcw0486
 * @문제이해
 * 수열 A가 주어질 때 가장 긴 증가하는 부분 수열을 구하자.
 * @알고리즘
 * 이분탐색
 * @접근방법
 * 우리가 집중해야되는건 '가장 긴 증가하는 수열'이 된다.
 * 즉, 증가하는 수열의 길이가 중요하다.
 * 1 2 5 10 9 라고 했을 때
 * 1 2 5 10 이나 1 2 5 9 나 길이면에선 같다는 의미이다.
 * 길이에 집중해서 문제를 풀어보도록 하자.
*/
public class Main {
    static int length =0;
    static int[] possible;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        int N = Integer.parseInt(br.readLine());
        possible = new int[N];
        length =0;
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            int num = Integer.parseInt(st.nextToken());
            if (length==0 || possible[length-1] < num) {
                possible[length++] = num;
            }else
                findPosition(0, length, num);
        }
        System.out.println(length);
    }

    public static void findPosition(int left, int right, int value) {
        int l = left;
        int r = right-1;
        int mid =0;
        while (l <= r) {
            mid = (l+r)>>1;
            if (possible[mid] <value) {
                l = mid +1;
            }else{
                r = mid-1;
            }
        }
        possible[l] = value;
    }
}