백준 12015 가장 긴 증가하는 부분 수열 2 Python 3

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

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

 

최종 코드

• GitHub -> https://github.com/hwayeon351/BEAKJOON-Algorithms/blob/main/BJ12015.py

GitHub - hwayeon351/BEAKJOON-Algorithms: 백준 알고리즘 소스 코드 모음

import sys
from bisect import bisect_left
input = sys.stdin.readline
N = int(input())
arr = list(map(int, input().split()))
lis = []
for num in arr:
    if len(lis) == 0: lis.append(num)
    else:
        loc = bisect_left(lis, num)
        if loc >= len(lis):
            lis.append(num)
        else:
            lis[loc] = num
print(len(lis))

---

풀이 과정

import sys
from bisect import bisect_left
input = sys.stdin.readline
N = int(input())
arr = list(map(int, input().split()))
lis = []
for num in arr:
    if len(lis) == 0: lis.append(num)
    else:
        loc = bisect_left(lis, num)
        if loc >= len(lis):
            lis.append(num)
        else:
            lis[loc] = num
print(len(lis))
#시간복잡도 = O(NlogN), 공간복잡도 = O(N)