[12015] 가장 긴 증가하는 부분 수열2

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

12015번: 가장 긴 증가하는 부분 수열 2

dp를 통해서 풀게 되면 수열의 크기 때문에 시간 초과가 일어난다. 문제의 힌트에 이분 탐색을 이용하라고 되어있어 어느 부분에 이분 탐색을 적용할 수 있는지 고민해보았지만 다른 풀이를 확인하고 나서 알았다.

 

풀이

최장 증가수열을 담을 배열 arr을 생성 후 입력받은 수열을 순서대로 탐색하면서 해당 숫자가 배열의 마지막 숫자보다 큰 경우, 배열에 추가해주고 작은 경우, 이분 탐색을 통해 수열의 숫자보다 작은 숫자를 찾으면 해당 위치로 들어가면 된다.

주의할 점은 해당 배열은 정답 배열과 크기만 같지 원소는 다르므로 최장 증가수열을 반환하는 문제에는 오답처리를 받게 된다.

 

정답 코드