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

문제 설명

1. N이 주어진다.

2. N개의 배열들에 해당하는 숫자들이 각각 주어진다.

3. 가장 긴 증가하는 부분 수열을 구하면 된다.

풀이 과정

 1. 처음에는 DP로 풀려 하였는데, 시간 복잡도에서 문제가 발생했다. 이후 DP와 이분탐색을 섞어서 해결하였다.

 2. 부분 수열을 저장할 Arraylist를 만들어, 이를 채워 준다.(이걸 쓴 이유는, 부분 수열의 경우 언제까지 값이 있을지 모르기도 하고, 중간에 값을 바꾸려고 하기 때문이다.)

 3. 숫자를 순서대로 입력받으며, 현재 입력된 순서의 숫자가 Arraylist의 가장 위의 값보다 큰 값인지 확인한다.

 4. 이후, 그 값이 더 큰 값인 경우 배열을 추가해 주면 된다.

 4. 그렇지 않은 경우 배열 내부의 값들 중 해당 값보다 큰 수들 중 최소의 숫자를 바꾸어 준다.

( 이걸 바꾸어 주는 이유는 다음과 같다. )

숫자가 1 6 8 4 5 7 9  이렇게 입력되었을 때

1 6 8 9 보다는

1 4 5 7 9가 더 긴 수열이 된다.

즉, 배열의 내부에서 더 작은 수로 이루어져 있어야, 이후에 들어간 값들에서 큰 값을 만들 수 있는 경우가 더 많아진다.

 5. 4의 두번째 process를 이진 탐색으로, 작은 값이면 뒤로, 큰 값이면 앞으로 이동하며 진행하면 된다.

 6. 이렇게 해서 구해진 ArrayList의 크기를 구하면 된다.

 7. 참고로 ArrayList의 경우 첫 값이 있어야 뒤에 입력되는 것을 넣을 수 있으니, 절대 나올 수 없는 값인 -1로 세트해 주고, 결과인 전체 크기에서 이 -1의 크기를 빼 주었다.

코드