[BOJ] 백준 12015 가장 긴 증가하는 부분 수열 2 (Swift)

문제

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

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

풀이

https://dev-mandos.tistory.com/217

[BOJ] 백준 11053 가장 긴 증가하는 부분 수열 (Swift)

위 문제와 동일하지만, 입력의 크기가 다릅니다.
위 문제에서는 n이 1,000이여서 $O(n^2)$의 시간 복잡도로 풀어도 가능합니다.

하지만 이번 문제는 n이 1,000,000 이므로 더 효율적인 방법으로 풀이해야 합니다.

LIS를 $O(nlogn)$으로 풀이할 수 있는 방법으로, 이분탐색이 있습니다.

LIS의 마지막 값 보다 현재 넣을 수가 더 크다면 수열에 넣어줍니다.
그렇지 않다면 LIS에 있는 현재 넣을 수보다 가장 가까운 큰 수와 현재 넣을 수를 교체 시켜주는 방식으로 풀이할 수 있습니다.

현재 넣을 수보다 가장 가까운 큰 수를 구할 때, 이분 탐색을 사용해서 시간 복잡도를 $O(nlogn)$으로 만들 수 있습니다.

소스코드

후기

LIS의 길이를 구하는 방법 중 더 효율적인 방법이 있다는 것을 알게되었습니다.
자주 사용되는 알고리즘이라고 알고 있어서 꼭 알아야 할 알고리즘이라고 생각합니다.