[백준/12738/파이썬] 가장 긴 증가하는 부분수열 3

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

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

Problem

• 수열 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)

SOL

개념글에서는 binary search를 직접구현하는 연습을 했지만, 파이썬은 내장되어있는 친구를 쓰는게 더 빠르기 때문에, (편하기도 하고) bisect_left를 한번 써봤다.  (생각보다 편리하다)

개념은 똑같다. s가 들어갈 idx를 탐색해주고, Lis를 갱신시키는 방식이다. s가 들어가야할 자리(k)가 Lis의 길이보다 크거나, 같다면, Lis에 그대로 연결해주고 , 작다면, K에 S를 넣어준다.

#
import sys
input = sys.stdin.readline
from bisect import bisect_left

N = int(input())
seq = list(map(int, input().rstrip().split()))
Lis = []

for s in seq:
    k = bisect_left(Lis, s)
    #print("k:{},s:{},Lis:{}".format(k,s,Lis))
    if len(Lis) <= k:
        Lis.append(s)
        #print("k:{},s:{},Lis:{}".format(k,s,Lis))
    else:
        Lis[k] = s
        #print("k:{},s:{},Lis:{}".format(k,s,Lis))

print(len(Lis))