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

코드 풀이

이분 탐색 직접 구현하기

import sys
input = sys.stdin.readline

n = int(input())
num = list(map(int, input().split(' ')))

result = [num[0]]


def custom_bisect_left(sequence, number):
    start = 0
    end = len(sequence)
    while start < end:
        mid = (start + end) // 2
        if sequence[mid] < number:
            start = mid + 1
        else:
            end = mid

    return end


for i in range(1, n):
    if result[-1] < num[i]:
        result.append(num[i])
    else:
        result[custom_bisect_left(result, num[i])] = num[i]

    #print(result)

print(len(result))

bisect 모듈 이용하기

from bisect import bisect_left
import sys
N = int(sys.stdin.readline())

sequence = list(map(int, sys.stdin.readline().split(' ')))

result = [sequence[0]]

for i in range(1, N):
    if result[-1] < sequence[i]:
        result.append(sequence[i])
    else:
        result[bisect_left(result, sequence[i])] = sequence[i]
#print(result)
print(len(result))