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

 

두 번째 LIS 문제이다. 이전에 풀었던 문제와 같지만 범위가 1000에서 1000000으로 늘어났기 때문에 O(N²) 풀이법인 dp로 풀면 시간 초과가 나올게 분명하다. O(NlogN) 풀이의 핵심은 LIS를 구하는 것이 아니라 LIS의 길이만 구하는 것이다.

단지 길이만 구하는 것이기 때문에, 순회하면서 저장해둔 배열의 마지막 원소보다 크면 append해주고 작으면 덮어주는(?) 식으로 풀면 된다. 

##함수 선언 부분
import sys
input = sys.stdin.readline
##변수 선언 부분
A = []
dp = [0]
mid = 0
##메인 함수 부분
if __name__ == "__main__":
    N = int(input())
    A = [int(x) for x in input().split()]
    for i in range(N):
        left = 1
        right = len(dp) - 1
        if dp[-1] < A[i]:
            dp.append(A[i])
        else:
            while left <= right: 
                mid = (left + right) // 2
                if A[i] < dp[mid]:
                    right = mid - 1
                elif A[i] > dp[mid]:
                    left = mid + 1
                else: #같은 경우는 통과
                    mid = -1
                    break
            if mid == -1: #통과
                continue
            else: 
                dp[left] = A[i]
    print(len(dp)-1)

 

이전에 풀었던 방법이 O(NlogN)인 줄 알았지만 알고보니 O(N²)이었다.