[백준12738번] 가장 긴 증가하는 부분 수열 3 / Python3

문제

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.

예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.

입력

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다.

둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (-1,000,000,000 ≤ Ai ≤ 1,000,000,000)

출력

첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다.

예제 입력 1

6
10 20 10 30 20 50

예제 출력 1

4

나의 풀이

이 문제는 LIS를 구하는 알고리즘을 O(N^2)이 아닌 O(NlogN)으로 구현을 해야하는 문제로 lower_bound 를 이용하여 푸는 문제였습니다.

• Lower bound란, 이분탐색을 이용해서 오름차순으로 정렬된 배열에서 처음으로 특정 값 이상인 값이 나오는 인덱스를 반환해주는 함수입니다. 예를 몇가지 들면 아래와 같습니다.

  arr : [10, 20, 30, 40, 50]
  
  10 => 0
  15 => 1 

C++에서는 lower bound가 라이브러리로 제공되는 것 같지만 python의 경우 찾아보았지만 없는 것 같습니다. 따라서 직접 함수를 구현해줘야했습니다.

이 문제를 푸는 큰 흐름은 다음과 같습니다.

1. 입력으로 주어지는 배열의 숫자를 앞에서부터 탐색
2. 만약, 숫자가 answer 배열의 마지막 값보다 크다면 answer 맨 뒤에 삽입
3. 그렇지 않다면 lower bound로 answer에서의 해당 숫자가 들어갈 인덱스를 탐색

코드

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


def lower_bound(start, end, num):
    while start < end:
        mid = (start + end) // 2

        if answer[mid] < num:
            start = mid + 1
        else:
            end = mid
    return end


n = int(input())
arr = list(map(int, input().split()))

answer = []
for num in arr:
    if len(answer) == 0:
        answer.append(num)
        continue

    if answer[-1] < num:
        answer.append(num)
    else:
        idx = lower_bound(0, len(answer)-1, num)
        answer[idx] = num

print(len(answer))