[백준] 가장 긴 증가하는 부분 수열 2 / 자바 **

문제         

레벨: G2
알고리즘: 이분탐색
풀이시간: 1시간
힌트 참조 유무:  유

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

1 번째 시도   

[  LIS (Longest Increasing Subsequence) 란]
어떤 수열에서 만들 수 있는 부분 수열 중에서 가장 길면서 오름차순을 유지하는 수열이다.
LIS를 구할 때는 DP를 사용한다.
LIS의 길이를 구할 때는 이분 탐색(O(nlogn))을 사용한다. DP(O(n^2))로 길이를 구할 시 시간초과가 난다

[알고리즘 설명]
*이 알고리즘은 고정된 사고를 달리해서 이해해야 합니다*
핵심 아이디어: 길이가 동일한 증가 부분 수열 중에서 마지막 값이 작은 것을 유지합니다.

지금부터 배열을 순회하면 LIS를 찾아보도록 하겠습니다.
수열 A가 다음과 같다고 가정합니다: A = [5,6,1,2]

길이가 1인 LIS: {5} {6} {7} {1} {2}
길이가 2인 LIS: {5,6}  {1,2}

만약 A 뒤에 3이 온다면 {5,6} 배열은 3을 못담고 {1,2}배열만 담을 수 있습니다.
그래서 여기서 중요한 것은 가장 마지막 숫자가 낮을 수록 길이를 늘리는 데 유리하다 입니다.

그래서 우리는
길이가 1인 LIS는 {1} 이다라고 생각해야 하고
길이가 2인 LIS는 {1,2} 이다라고 생각해야 
A배열 뒤에 숫자 3이 오더라도 {1,2,3}이 올 수 있습니다. 

그래서 이 로직은 길이를 구하는데만 국한됩니다. 실제 LIS를 구하려면 이 방식을 사용하면 안된다.

[알고리즘 동작 예시]
수열 A가 다음과 같다고 가정합니다: A = [3, 5, 7, 9, 2, 1, 4, 8]

1. 초기 상태: - P = []
2. A의 각 원소에 대해 P 업데이트:
- A[0] = 3: P = [3]
- A[1] = 5: P = [3, 5]
- A[2] = 7: P = [3, 5, 7]
- A[3] = 9: P = [3, 5, 7, 9]
- A[4] = 2: P에서 2보다 크거나 같은 첫 번째 원소는 3 -> P = [2, 5, 7, 9]
- A[5] = 1: P에서 1보다 크거나 같은 첫 번째 원소는 2 -> P = [1, 5, 7, 9]
- A[6] = 4: P에서 4보다 크거나 같은 첫 번째 원소는 5 -> P = [1, 4, 7, 9]
- A[7] = 8: P에서 8보다 크거나 같은 첫 번째 원소는 9 -> P = [1, 4, 7, 8]

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

public class Main {
	static int N, ans, arr[];
	static ArrayList<Integer> lis;
	public static void main(String[] args) throws Exception {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		N = Integer.parseInt(br.readLine()); //수열의 크기
		arr = new int[N]; //수열
		lis = new ArrayList<>();
		
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		for (int i = 0; i < N; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}
		
		//LIS의 길이 구하기

		//각 원소가 LIS에 들어갈 위치를 찾는다.

		
		lis.add(0);
		
		for(int num : arr) {
			if(num > lis.get(lis.size()-1)) {
             			//리스트 마지막에 넣어야 되는 경우 => 뒤에 넣기
            			lis.add(num);
          		}
		
			else { //넣을 위치 찾는다
				int left = 0;
				int right = lis.size()-1;
				int mid = 0;
				
				while(left<right) {
					mid = (left+right)/2;
					if(lis.get(mid) < num) left = mid+1;
					else right = mid; 
				}
				
				lis.set(right, num);
			}
		}
		
		System.out.println(lis.size()-1);

	}
	
	
}