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

[문제 바로 가기] - 가장 긴 증가하는 부분 수열 2

📌 유형 : 이분탐색

이전에 풀었던 가장 긴 증가하는 부분 수열 4와 비슷한 문제인데, 이 문제는 수열의 크기 N이 최대 1,000,000까지기 때문에 이중 for문으로 풀이하면 시간초과가 난다.

따라서 이분탐색으로 O(NlogN)의 시간복잡도로 풀이해야 한다.

💡 아이디어

for문을 이용해서 새로운 수를 탐색하며 : O(N)

1. 현재 수가 마지막 값보다 크면 뒤에 붙인다
2. 작거나 같으면 이분 탐색으로 해당 수 이상인 첫 번째 값을 찾아서 교체한다 : O(log N)

3 4 1 2 8 5 6

위의 예제로 설명을 하면 다음과 같다.

• 3 넣기 : [3]
• 3보다 큼 -> 4 넣기 : [3, 4]
• 3보다 작음 -> 3 대신 1 넣기 : [1, 4]
• 4보다 작음 -> 4 대신 2 넣기 : [1, 2]
• 2보다 큼 -> 8 넣기 : [1, 2, 8]
• 8보다 작음 -> 8 대신 5 넣기 : [1, 2, 5]
• 5보다 큼 -> [1, 2, 5, 6]

답은 리스트의 크기인 4가 된다!

이분탐색은 직접 구현해도 되고 Collections.binarySearch()를 사용해도 된다. 이 문제를 풀어보면서 Collecetions.binarySearch()에 대해 알아보았다.

---

풀이

이분탐색 구현

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

/**
 * 백준 12015번 가장 긴 증가하는 부분 수열 2
 * - 이분탐색
 */

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int N = Integer.parseInt(br.readLine());
		int[] num = new int[N];
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		for (int i = 0; i < N; i++)num[i] = Integer.parseInt(st.nextToken());
		
		List<Integer> list = new ArrayList<>();
		
		for (int i = 0; i < N; i++) {
			if (list.isEmpty() || list.get(list.size() - 1) < num[i]) list.add(num[i]);
			else {
				int left = 0;
				int right = list.size() - 1;
				
				while (left < right) {
					int mid = left + (right - left) / 2;
						
					if (list.get(mid) >= num[i]) {
						right = mid;
					} else {
						left = mid + 1;
					}
				}
					
				list.set(left, num[i]); // 해당 인덱스 값 교체
			}
		}
		
		System.out.println(list.size());
	}
}

Collections.binarySearch() 사용

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.StringTokenizer;

/**
 * 백준 12015번 가장 긴 증가하는 부분 수열 2
 * - 이분탐색
 */

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int N = Integer.parseInt(br.readLine());
		int[] num = new int[N];
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		for (int i = 0; i < N; i++) num[i] = Integer.parseInt(st.nextToken());
		
		List<Integer> temp = new ArrayList<>();

		for (int x : num) {
		    int idx = Collections.binarySearch(temp, x);
		    
		    if (idx < 0) {
		        idx = -(idx + 1);
		    }
		    
		    if (idx == temp.size()) {
		        temp.add(x);
		    } else {
		        temp.set(idx, x);
		    }
		}

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