[BOJ 12015/파이썬]가장 긴 증가하는 부분 수열2

0. 문제 링크

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

1. 문제

2. 문제해결 알고리즘

이분탐색

바이토닉 정렬

3. 문제 해결 및 코드

이 문제의 핵심은 부분 수열이 아니라 부분 수열의 개수이다.

import sys
from bisect import bisect_left

input = sys.stdin.readline

def main():
	N = int(input())
	arr = list(map(int, input().split()))
	
	stack = [0]
	
	for n in arr:
		if stack[-1] < n:
			stack.append(n)
		else:
			stack[bisect_left(stack, n)] = n
	
	print(len(stack) - 1)

main()

수열에 가장 마지막에 넣은 수 보다 크다면, 배열에 넣고 

그렇지 않다면, 넣을려는 수보다 직전으로 큰 수를 대체 한다.

직전으로 큰 수란 다음을 의미한다.

예를 들어서 [1, 2, 3, 7, 8, 9] 에서 5를 넣는다고 가정하자.

5보다 직전으로 큰 수는 7을 의미한다. 즉 수열 속에 있는 숫자들 중에서 5보다 큰 수 중 가장 작은 값을 의미한다.

여기서 bisect 함수 대신에 직접 이분탐색을 구현해서 해도 무방하다.

bisect 함수가 이분탐색 알고리즘으로 작동 되기 떄문이다.