boj.kr/12015 가장 긴 증가하는 부분 수열 2 (gold2) 파이썬 풀이

1. LIS(Longest Increasing Subsequence) 배열에 원본 수 배열 A의 첫번째 요소를 추가한다.

2. 원본 수 배열 A를 마지막 요소까지 순회하면서 아래 3-4를 반복한다.

3. LIS의 마지막으로 추가된 요소보다 원본 수 배열 A의 요소 a가 더 크면 LIS에 추가한다.

4. LIS의 마지막으로 추가된 요소보다 원본 수 배열 A의 요소 a가 더 작거나 같으면 LIS에서 왼쪽부터 순회하면서 a와 같거나 더 큰 숫자가 있는 첫번째 index에 a를 저장한다 

5. LIS의 길이를 출력한다 

 

N = int(input())
A = list(map(int, input().split()))

LIS = []
LIS.append(A[0])

from bisect import bisect_left

for a in A:
    if a > LIS[-1]:
        LIS.append(a)
    else:
        LIS[bisect_left(LIS, a)] = a

print(len(LIS))

 

bisect_left를 사용함으로써 LIS 배열의 마지막 요소가 a보다 컸던 경우에 a가 LIS의 마지막-1번 요소보다 큰 것을 보장하면서 이후 요소들에 대해 a보다 더 큰 요소를 추가해야 한다. 왜냐하면 그렇게 함으로써 LIS 배열의 각 요소들은 가장 긴 증가하는 부분수열과 다를 수 있지만, 길이는 동일한 것이 보장되기 때문이다.

 

참고출처

"[백준 12015 파이썬] 가장 긴 증가하는 부분 수열 2 (골드2, 이분 탐색)", velog.io/@ledcost, 2022년 1월 5일 수정, 2023년 5월 27일 접속, https://velog.io/@ledcost/백준-12015-파이썬-가장-긴-증가하는-부분-수열-2-골드2-이분-탐색.