|
from bisect import bisect_left
n = int(input())
l = list(map(int,input().split()))
order = [0 for i in range(n)]
order[0] = 1
table = [l[0]]
for i in range(1, n) :
if table[-1] < l[i] :
table.append(l[i])
order[i] = len(table)
else :
order[i] = bisect_left(table, l[i]) + 1
table[order[i] - 1] = l[i]
m = max(order)
print(m)
lis = []
for i in range(n) :
if order[n-1-i] == m :
lis.append(l[n-1-i])
m = m - 1
for i in range(len(lis)) :
print(lis[len(lis)-1-i], end = ' ')
|
14002와 마찬가지로 부분수열의 길이뿐 아니라 수열 자체도 출력해야 하는 문제이다.
그런데 이제 (1 ≤ N ≤ 1,000,000)과 (-1,000,000,000 ≤ Ai ≤ 1,000,000,000)을 곁들인
일단 큰 range를 다루니, 12738처럼 이분탐색을 써야 할 것이다.
그런데 12738의 코드(https://uneducatedjungler.tistory.com/48)는 table이라는 부분수열 리스트가 있긴 하지만
else(다음 원소가 [-1]보다 크지 않은 경우)에도 원소를 버리지 않고 다음 체크를 위해 저장한다.
즉 table의 길이는 가장 긴 부분수열의 길이로 유지되지만, table 원소는 부분수열의 원소가 아니다.
따라서 이번 문제도 14002(https://uneducatedjungler.tistory.com/49)처럼, 각 원소가 부분수열에서 몇 번째 원소에 해당하는지 order를 기록하여 그 order 리스트를 이용해 부분수열을 직접 만들어야 한다.
12738이랑 14002의 코드가 같이 잘 돌아가도록 합치면 끝
대충 풀어도 풀리는 1번 문제
1번보다 range가 넓어져서 이분탐색을 써야하는 2, 3번 문제
수열의 출력을 요구해서 부분수열의 order를 기록해야 하는 4번 문제
그리고 마지막으로 2,3번 문제에 4번의 order까지 적용해야 풀 수 있는 5번 문제
시리즈(?) 구성이 꽤 괜찮은 것 같다.
'Week 01 ~ 04 : 알고리즘 문제 풀이' 카테고리의 다른 글
| 파이썬 백준 11286 절댓값 힙 (0) | 2021.11.17 |
|---|---|
| 파이썬 백준 1927 최소 힙 (0) | 2021.11.17 |
| 파이썬 백준 14002 가장 긴 증가하는 부분 수열 4 (0) | 2021.11.17 |
| 파이썬 백준 12738 가장 긴 증가하는 부분 수열 3 (0) | 2021.11.17 |
| 파이썬 백준 12015 가장 긴 증가하는 부분 수열 2 (0) | 2021.11.17 |