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

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

아이디어

앞에서 풀어본 백준 11053번: 가장 긴 증가하는 부분 수열에서는 원소 하나의 길이를 결정할 때마다 앞에 있는 모든 값을 탐색해야만 했다. 따라서 시간복잡도는 O(N^2)인데 이러한 방법으로는 입력의 크기가 1,000,000인 12015번 문제를 풀 수 없다. 따라서 시간복잡도를 줄여야 한다.

어디서 시간복잡도를 줄이면 좋을까? 앞의 모든 원소를 탐색할 필요가 있을까? 11053번을 풀 때는 dp테이블에 해당 값이 가질 수 있는 최대한의 길이를 기록했지만, 이번에는 테이블에 오름차순으로 해당 길이(index)를 만들 수 있는 가장 작은 값을 기록한다. 예를 들어, 테이블의 두 번째 인덱스에는 길이를 2로 만들 수 있는 가장 작은 값이 기록될 것이다.

처음에 주어진 수열에서 두 번째 값까지 탐색했을 때 길이를 2로 만들 수 있는 가장 작은 값은 6이다. 그러나 세 번째 값까지 탐색했을 때 길이를 2로 만들 수 있는 가장 작은 값은 2가 된다. 동일한 방법으로, 네 번째 값까지 탐색했을 때 길이를 3으로 만들 수 있는 가장 작은 값은 4이다. 그러나 여섯 번째 값까지 탐색했을 때 길이를 3으로 만들 수 있는 가장 작은 값은 3이 된다.

코드

N = int(input())
arr = list(map(int, input().split()))
arr.insert(0, 0)
checkLength = [0]


def binarySearch(array, value, low, high):
    if low > high:
        return low
    mid = (low+high) // 2
    if array[mid] > value:
        return binarySearch(array, value, low, mid-1)
    elif array[mid] < value:
        return binarySearch(array, value, mid+1, high)
    else:
        return mid


for i in range(1, N + 1):
    targetIndex = binarySearch(checkLength, arr[i], 0, len(checkLength) - 1)
    if targetIndex >= len(checkLength):
        targetIndex -= 1
    if checkLength[targetIndex] >= arr[i]:
        checkLength[targetIndex] = arr[i]
    else:
        if targetIndex == len(checkLength) - 1:
            checkLength.append(arr[i])


print(len(checkLength) - 1)

여담

Binary Search 까먹어서 구글에 검색해봤다. 이정도는 안보고 구현할 수 있어야 하지 않을까? 반성중이다.