11053번, 12015번 - 가장 긴 증가하는 부분 수열

1️⃣ 이분탐색

 

✏️ 풀이 과정

해결 아이디어는 C라는 배열에 차례대로 입력값을 넣어가면서 수열을 업데이트하는것입니다. 이 때 이분탐색이 이용되는데 어떤 수를 넣을 때 이분탐색을 통해서 C의 어떤 자리에 이 수를 넣어야 하는지 체크합니다. 만약 이 자리가 기존에 채워져있는 인덱스일 경우(더 큰 수가 있는 경우가 해당됩니다.) 해당 수를 교체합니다. 이렇게 하면 해당 자리의 수가 작아지기 때문에 결과적으로 나중에 더 길어질 때 더 작은 수들을 채워넣을 여력이 생기게 됩니다.(중간 부분이 실제 수열과 달라지겠지만 길이 자체는 같습니다.)  그리고 채워지지 않은 인덱스인 경우(가장 큰 경우) 해당 자리에 넣고 사이즈를 증가시켜줍니다.

 

C 배열은 항상 오름차순으로 정렬되기 때문에 추가적인 정렬 없이도 항상 이분탐색을 실행할 수 있습니다. 

 

⏱ 시간 복잡도

이분 탐색을 N번 실시하기 때문에 O(NlogN)이 됩니다.

 

💻 코드

Java

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

public class Main{
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		int N = Integer.parseInt(br.readLine());
		int[] arr = new int[N];
		int[] C = new int[N];
		st = new StringTokenizer(br.readLine());
		int size = 0;
		int pos;
		for (int i = 0; i < N; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
			pos = Arrays.binarySearch(C, 0, size, arr[i]);
			if(pos >= 0) {
				continue;
			}
			pos = -1 * (pos + 1);
			C[pos] = arr[i];
			if(pos == size) {
				size++;
			}
		}
		System.out.println(size);
		br.close();
	}
}