[Python] 백준 12015번 문제, 가장 긴 증가하는 부분 수열 2

<문제 링크>

 

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

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

 

---

<풀이>

 

주어진 수열에서 가장 긴 증가하는 부분 수열을 구하는 문제인데 입력 크기가 1 ≤ N ≤ 1,000,000이기 때문에 DP 방식으로 풀면 n^2의 시간 복잡도를 가져 시간 초과가 발생한다.

그래서 최장 증가 부분 수열(LIS) 알고리즘을 사용해야 하며, log n이라는 시간 복잡도를 가지는데 N만큼 동작해야 하므로 최종 시간 복잡도는 NlogN이다.

A는 1부터 1,000,000까지의 범위이므로 LIS 초기값을 0으로 초기화한 다음에 LIS의 마지막 원소보다 n이 크다면 그대로 append 해주고 n이 크지 않다면, 이분 탐색을 통해 어느 위치에 삽입될 지 탐색한다.

이분 탐색을 사용하며 mid를 구해 mid 값이 n보다 작으면 오른쪽을 탐색하고, n보다 크면 왼쪽을 탐색한다.

그래서 최종적으로 LIS는 초기값인 0을 가지고 있으므로 출력문에서 len(LIS) - 1를 해준다.

if __name__ == "__main__":
    N = int(input())
    arr = list(map(int, input().split()))
    LIS = [0]

    for n in arr:
        if LIS[-1] < n:
            LIS.append(n)
        else:
            left = 0
            right = len(LIS)

            while left < right:
                mid = (left + right) // 2

                if LIS[mid] < n:
                    left = mid + 1
                else:
                    right = mid

            LIS[right] = n

    print(len(LIS) - 1)