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

문제

수열 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의 가장 긴 증가하는 부분 수열의 길이를 출력한다.

아이디어

맨 앞(0번 인덱스)보다 큰 수들을 count 시킨다. (wrong)

코드

Mine (Wrong)

import sys
input = lambda : sys.stdin.readline()

N = int(input()) #수열의 길이
A = list(map(int, input().split())) #수열
temp = 0 #현재까지 탐색된 최대 숫자값
ans = 0

for i in range(N):
    if temp < A[i]:
        ans += 1
        temp = A[i]
print(ans)

개선사항

맨 앞(0번 인덱스)가 큰 수라면, 0번 인덱스를 포함하는 부분 수열은 최대 길이가 아니다.
ex) 50, 10, 20, 30, 40, 60
code -> [50, 60]
ans -> [10, 20, 30, 40, 60]

아이디어(bisect)

Mine

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의 마지막(최대값)과 새로운 값 비교
        lis.append(num)
    else:
        index = bisect_left(lis, num)
        lis[index] = num

print(len(lis))

아이디어 출처 : https://velog.io/@uoayop/BOJ-12015-%EA%B0%80%EC%9E%A5-%EA%B8%B4-%EC%A6%9D%EA%B0%80%ED%95%98%EB%8A%94-%EB%B6%80%EB%B6%84-%EC%88%98%EC%97%B4-2-Python

개선사항

bisect 사용법 - https://programming119.tistory.com/196