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

<문제 링크>

 

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

12738번: 가장 긴 증가하는 부분 수열 3

 

---

<풀이>

 

가장 긴 증가하는 부분 수열 시리즈 중 세번째 문제이며, 주어진 수열에서 가장 긴 증가하는 부분을 구하는 것인데 입력의 크기가 1 ≤ N ≤ 1,000,000 이기 때문에 기존의 풀이법인 동적 프로그래밍(Dynamic Programming)을 사용한다면 n^2의 시간 복잡도를 가지기 때문에 시간 초가로 실패한다.

따라서 DP 알고리즘이 아닌 최장 증가 부분 수열(LIS) 알고리즘을 사용해 풀어야 한다. LIS 알고리즘은 한 번 작동 시 log n의 시간 복잡도를 가지며 수열 길이인 N만큼 작동해 총 nlogn의 시간 복잡도를 가진다.

LIS 배열에 가장 긴 증가하는 부분 수열이 담기기 때문에 처음에는 A[0]로 초기화한다.

# 1: 0부터 확인하기 때문에 반복문은 1부터 N까지 작동

# 2: 긴 증가하는 부분 수열이라면 바로 추가

# 3: 그렇지 않다면 이분 탐색으로 어디에 넣을지 위치 탐색

# 4: left가 right보다 같거나 커질 때까지 탐색하며, 부분 수열 중앙값이 n보다 작으면 오른쪽 탐색, n보다 크면 왼쪽 탐색해서 최종적으로 구한 위치에 n 삽입

if __name__ == "__main__":
    N = int(input())
    A = list(map(int, input().split()))
    LIS = [A[0]]
    
    # 1
    for n in A[1:]:
        # 2
        if LIS[-1] < n:
            LIS.append(n)
        else: # 3
            left = 0
            right = len(LIS)-1
            
            # 4
            while left < right:
                mid = (left + right) // 2

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

            LIS[right] = n

    print(len(LIS))