Backdrop

백준 온라인 저지 ▸ 12015

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

문제

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

예제 입력 1

6
10 20 10 30 20 50

예제 출력 1

4

풀이

python

이분 탐색을 이용해서 문제를 풀 수 있어요. 스택을 생성하고, 배열을 순회하면서 다음과 같은 조건을 확인해요.

  1. 스택의 top이 현재 숫자보다 작으면, 현재 숫자를 스택에 넣어요.
  2. 스택의 top이 현재 숫자보다 크거나 같으면, 이분 탐색을 이용해서 현재 숫자보다 크거나 같은 수 중 가장 작은 수를 찾아 현재 숫자로 바꿔요.

스택은 항상 오름차순으로 정렬되어 있기 때문에, 이분 탐색을 이용해서 스택에 넣을 위치를 찾을 수 있어요.

배열: 30 50 10 10 20 30
스택: 30
배열: 30 50 10 10 20 30
스택: 30 50
배열: 30 50 10 10 20 30
스택: 10 50
배열: 30 50 10 10 20 30
스택: 10 50
배열: 30 50 10 10 20 30
스택: 10 20
배열: 30 50 10 10 20 30
스택: 10 20 30

코드

from bisect import bisect_left
 
 
n = int(input())
a = list(map(int, input().split()))
 
stack = [a[0]]
for i in range(1, n):
    if a[i] > stack[-1]:
        stack.append(a[i])
    else:
        stack[bisect_left(stack, a[i])] = a[i]
 
print(len(stack))