가장 긴 증가하는 부분 수열 3 (12738번) - 백준 (BOJ)

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

12738번: 가장 긴 증가하는 부분 수열 3

 

백준 - 가장 긴 증가하는 부분 수열 3 (12738번)

 

난이도 : Gold 2

알고리즘 : Binary Search

풀이 소요 시간 : 5 mins

Time Complexity : O( N * log(N) )

 

from bisect import bisect_left


if __name__ == '__main__':
    N = int(input())
    stack = []
    for a in map(int, input().split()):
        idx = bisect_left(stack, a)
        if idx == len(stack):
            stack.append(a)
        else:
            stack[idx] = a
    print(len(stack))

 

이진 탐색 (Binary Search) 를 통해서

현재 숫자가 들어갈 수 있는 위치를 찾아서 업데이트 하면 된다.

 

---

 

전에 거의 동일한 문제를 푼 적 있어서,

풀이법을 알고 있었다.

 

방법만 알면 코드 구현은 정말 간단하기 때문에

5분컷이 가능했다.