백준 12015 - 가장 긴 증가하는 부분 수열 2

문제

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

---

조건

• 수열 A가 주어졌을 때 가장 긴 증가하는 부분 수열을 구해야 함.
• 수열의 최대 길이는 100만
• 이전에 풀었던 dp 방식으로 풀 경우 시간 복잡도 O(n^2)이므로 시간 초과가 뜬다.
• 어떻게 풀어야 할까??

---

접근법

솔직히 이 문제를 어떻게 이분 탐색으로 풀어야 할지 감이 안왔고 자바 근본 알고리즘 블로그 stranger's lab님의 풀이법을 보고 풀었다. 볼 때 마다 풀이법과 설명 방식에 감탄한다.

https://st-lab.tistory.com/285

알아야 할 것 - 이진 탐색 (Lower Bound)

lower bound (하한)

• 배열에서 찾고자 하는 값 이상이 처음 나타나는 위치(인덱스)

upper bound (상한)

• 배열에서 찾고자 하는 값 보다 큰 값이 처음 나타나는 위치(인덱스)

https://bajamircea.github.io/coding/cpp/2018/08/09/lower-bound.html

Lower Bound 구현

			int start = 0;
			int end = arr.length;
			int value = ? // 찾고자 하는 값

			while (start < end) {
				int mid = (start + end) / 2;

				//end를 mid로 좁힌다.
				if (arr[mid] >= value) {
                	end = mid;
          		} 
                //start를 mid+1로 좁힌다.
                else {
                	start = mid + 1;
          		}
			 }

[10, 20, 30, 15, 20, 30, 50, 40, 45 ,60] 배열의 LIS를 구한다 가정

현재 값	dp	결과
10		[10]
20	[10]	[10, 20]
30	[10, 20]	[10, 20, 30]
15	[10, 20, 30]	[10, 15, 30]
20	[10, 15, 30]	[10, 15, 20]
30	[10, 15, 20]	[10, 15, 20, 30]
50	[10, 15, 20, 30]	[10, 15, 20, 30, 50]
40	[10, 15, 20, 30, 50]	[10, 15, 20, 30, 40]
45	[10, 15, 20, 30, 40]	[10, 15, 20, 30, 40, 45]
60	[10, 15, 20, 30, 40, 45]	[10, 15, 20, 30, 40, 45, 60]

15를 어떻게 저장해야 할까??

• 일단 현재까지 dp 배열에 저장된 최대값(30)보다 작다.
• 그러면, 15가 들어갈 수 있는 15보다 크거나 같은 값을 갖는 첫번째 인덱스를 찾는다. (이분 탐색 - lower bound)
• 해당 인덱스의 값을 15로 변경
• 이 문제의 목적은 LIS 배열 값을 구하는 것이 아니라 길이를 구하는 것이다.
• 15로 값을 바꾼다고 현재까지의 LIS 길이에 변화는 없다.
• 단지, 이후에 LIS 배열에 더 많은 값이 들어올 경우를 생각해야하므로 값을 바꿔놓는 것이다.
• 어떻게 이런 생각을 하지...????

1. 현재 값이 dp 배열에 저장된 최대값보다 작다면 해당 값으로 대체할 수 있는 인덱스를 찾는다. (이분탐색)
2. 해당 인덱스의 값을 현재 값으로 변경한다.
3. 현재 값이 dp 배열에 저장된 최대값보다 크다면 dp 배열의 최대값을 갱신한다.

---

문제 풀이

public class p12015 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        int N = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine());

        int[] arr = new int[N];
        int[] dp = new int[N];

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

        dp[0] = arr[0];
        int LIS_length = 1;

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

            if(dp[LIS_length-1]<arr[i]) {
                dp[LIS_length] = arr[i];
                LIS_length++;
            }

            else {
                int start = 0;
                int end = LIS_length;

                while (start < end) {
                    int mid = (start + end) / 2;

                    if (dp[mid] >= arr[i]) {
                        end = mid;
                    }
                    else {
                        start = mid + 1;
                    }
                }
				dp[start] = arr[i];
            }
        }

        System.out.println(LIS_length);

    }
}