백준 - 12015 가장 긴 증가하는 부분 수열2 [이분탐색]

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

1. 문제유형

• Binary Search, DP

2. 자료구조

• lis (list): 최장 부분 순열을 저장하는 리스트
• a (int): n개의 입력값을 저장하는 리스트

3. 해결과정

1. 입력받은 값을 a에서 하나씩 꺼낸다.
2. lis가 비어 있으면 꺼낸 값을 추가한다.
3. 비어있지 않고, lis[-1] < num이면 꺼낸 값을 추가한다.
4. 꺼낸 값이 lis의 마지막 값보다 작으면 이분탐색으로 들어갈 index를 찾고 덮어씌운다.
5. 반복이 끝나면 lis의 길이를 출력한다.

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

n = int(input())
a = list(map(int, input().split()))
lis = []

for num in a:
    if not lis:
        lis.append(num)
        continue
    if lis[-1] < num:
        lis.append(num)    
    else:
        index = bisect_left(lis, num)
        lis[index] = num
print(len(lis))