해결 방법

1. 이분탐색으로 수열을 만들어 나가며 답을 도출한다.

2. 이분 탐색 종류 중 LowerBound를 이용하여 인덱스를 탐색한다.

알고리즘

1.vector에 데이터가 없으면 삽입한다.

2.vector의 최대값보다 크면 삽입한다.

3.vector의 최대값보다 작으면 LowerBound를 이용해 인덱스를 찾고, 그 값을 교체해준다.

예시

{10, 1, 2, 20, 40, 5 }

1) vector = {10}

2) vector = {1}

3) vector = {1, 2}

4) vector = {1, 2, 20}

4) vector = {1, 2, 20, 40}

4) vector = {1, 5, 20, 40}

나의 문제점

LowerBound 구현이 완벽하지 않아서 인덱스 값을 잘못 가져왔고 런타임 에러가 발생했다.

LowerBound : value 값 보다 크거나 같은 값 중 첫 번째 인덱스를 찾는 알고리즘

ex ) [1, 1, 3, 4, 5, 5, 7, 7, 9]

value => 6 의 LowerBound 결과 index = 6

value => 5 의 LowerBound 결과 index = 5

구현 코드

import java.io.IOException;
import java.util.*;

public class Main {
	static Vector<Integer> vector;

	public static void main(String[] args) throws IOException {
		Scanner sc = new Scanner(System.in);
		vector = new Vector<>();
		int N = sc.nextInt();

		for(int i=0; i<N; i++) {
			int value = sc.nextInt();
			int maxIndex = vector.size();
			
			if(maxIndex == 0 || vector.elementAt(maxIndex - 1) < value) {
				vector.add(value);
			}
			else binarySearch(value);
		}
		
		System.out.println(vector.size());
	}
	
	public static void binarySearch(int insertValue) {
		int index = lowerBound(insertValue);
		
		vector.remove(index);
		vector.add(index, insertValue);		
		
	}
	public static int lowerBound(int insertValue) {
		int start = 0;
		int end = vector.size() - 1;
		
		while(start <= end) {
			int mid = (start + end) / 2;
			
			if(vector.elementAt(mid) < insertValue) {
				start = mid + 1;
			}
			else {
				end = mid - 1;
			}
			
		}
		return start;
	}
	
}