[백준] 14003. 가장 긴 증가하는 부분 수열 5 - Python

[Platinum V]

 

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

14003번: 가장 긴 증가하는 부분 수열 5

 

풀이

이분 탐색(Binary Search)를 이용해, log(n logN)의 시간 복잡도로 풀어내는 LIS 문제에서,

LIS 배열까지 구해야 한다.

 

입력된 배열을 순회하며, res 배열의 몇 번째 index에 들어가는 지를 모든 원소에 대해 기록하고, (res_idx)

res_idx 배열을 거꾸로 순회하면서, index가 가장 처음 나오는 부분을 따와 배열에 저장한다.

예를 들어, LIS의 길이가 5라면, index는 0, 1, 2, 3, 4일 것이므로,

res_idx 를 거꾸로 순회하면서 나오는 제일 첫 번째 4가 나오는 자리의 숫자를 queue에 삽입.

그리고 그 4보다 더 왼쪽에 있는 제일 첫 번째 3이 나오는 자리의 숫자를 queue에 삽입.

그리고 그 3보다 더 왼쪽에 있는 제일 첫 번재 2가 나오는....~~

 

자세한 설명은, 다른 블로그에서 더 잘 써놓았을 것이므로 생략. 나보다 설명 잘하는 다른 사람들이 너무 많아~

 

AC.

import bisect
from collections import deque
n = int(input())

lines = list(map(int, input().split()))

res = []
res_idx = []
for i in lines:
    a = bisect.bisect_left(res, i)
    if a == len(res):
        res.append(i)
    else:
        res[a] = i
        
    # 원소가 res 배열에 들어가는 index 저장.
    res_idx.append(a)

cnt = len(res)-1
q = deque()
# index 배열을 거꾸로 순회하며, 3인 원소를 찾고, 3인 원소 전에 있는 2인 원소를 찾고.. 반복.
for i in range(len(res_idx)-1, -1, -1):
    if res_idx[i] == cnt:
        cnt -= 1
        q.appendleft(lines[i])
        
print(len(q))
print(*q)