[백준] 12738. 가장 긴 증가하는 부분 수열 3 (Java)

 

문제

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

 

알고리즘

이분 탐색

 

풀이

가장 긴 증가하는 부분 수열 2 문제에서 입력 값의 범위만 늘어났다.

하지만 늘어난 범위도 int 형 범위 안에 들어가기 때문에 그대로 해결된다.

 

 

코드

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

public class Main {
	static ArrayList<Integer> list;

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		list = new ArrayList<>();
		int N = Integer.parseInt(br.readLine());
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		for (int i = 0; i < N; i++) {
			int num = Integer.parseInt(st.nextToken());
			if (i == 0 || list.get(list.size() - 1) < num)
				list.add(num);
			else
				list.set(lowerBound(num), num);
		}

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

	static int lowerBound(int num) {
		int left = 0;
		int right = list.size();

		while (left < right) {
			int mid = (left + right) / 2;

			if (list.get(mid) < num) left = mid + 1;
			else right = mid;
		}

		return right;
	}
}