[코딩 테스트 연습(파이썬/Python)] 백준 12015번 _ 가장 긴 증가하는 부분 수열 2

https://www.acmicpc.net/problem/12015

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

[문제]

수열 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) 수열을 차례로 탐색하면서, 작은 순서대로 쌓는다.

2) 이때 쌓는 방법은 이전까지 쌓은 수열에 대해 현재 숫자가 위치해야할 인덱스를 이분 탐색(bisect)으로 구하고 해당 위치를 변경하는 것으로 한다.

3) 최종적으로 쌓인 수열의 길이가 구하고자 하는 LIS의 길이가 된다.

 

import bisect as bi
n = int(input())
a = list(map(int, input().split()))
INF = int(1e9)
inc_arr = [INF]*n

for i, x in enumerate(a):
    idx = bi.bisect_left(inc_arr,x)
    inc_arr[idx] = x
    
print(bi.bisect_left(inc_arr,INF))

충분히 큰 수로 수열을 초기화하고, 각 수열이 위치할 곳을 찾아 대체해주면 된다.

import bisect as bi
input()
a = []
for x in map(int, input().split()):
    i = bi.bisect_left(a, x)
    a[i:i + 1] = [x]
print(len(a))

파이썬 list가 슬라이싱을 통해서도 할당이 가능하다는 것을 이용하면, 보다 간단한 코드로도 같은 구현을 할 수 있다.