[파이썬] 백준 12015번 가장 긴 증가하는 부분 수열 2

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

시간 제한

1초

 

메모리 제한

512MB

문제

수열 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 ≤ Ai ≤ 1,000,000)

출력

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

예제 입력 1 

6
10 20 10 30 20 50

예제 출력 1 

4

---

나의 풀이

기존 수열로만 처리하려면 모든 원소(idx)와 그 후속 원소(idx + 1 ...) 에 대해서 확인해야 하기 때문에 $O(N^2)$의 시간 복잡도가 발생한다.

이때, N = 1,000,000이므로 시간 초과가 발생할 것이다.

 

따라서 문제를 해결하기 위해선 기존 수열에서 확인하지 않고 별도의 최장 정렬 수열을 구성해야 한다. 

이때, 최장 정렬 수열을 구성할 때 새로운 값의 위치를 binary search를 통해서 구성할 수 있다.

import sys

def parametric_search(array : list, target : int):
    start = 0
    end = len(array) - 1
    # 결과 저장
    result = 0
    # target이 위치하려면 array[mid] 보다 커야 함.
    while start <= end:
        mid = (start + end) // 2
        # 조건 만족시키기 위해서 이동
        if array[mid] < target:
            start = mid + 1
        # 조건 만족하는 최적 위치 찾기
        else:
            result = mid
            end = mid - 1        
    return result

        

array_len = int(input())
array = list(map(int,sys.stdin.readline().rstrip().split()))

# 증가 수열을 구성할 새로운 배열 생성
longest_array = [array[0]]
for i in array[1:]:
    last_num = longest_array[-1]
    # 새로 입력된 수가 더 큰 경우 바로 입력
    if i > last_num:
        longest_array.append(i)
    # 새로 입력된 수가 더 작을 경우 idx를 binary search를 통해서 구함.
    else:
        longest_array[parametric_search(longest_array, i)] = i
    
print(len(longest_array))

 

참고한 아이디어

LIS (Longest Increasing Subsequence) - 최장 증가 부분 수열