[백준] 14003 가장 긴 증가하는 부분 수열 5, python

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

 

 

 

[백준] 12738 가장 긴 증가하는 부분 수열 3

[백준] 12738 가장 긴 증가하는 부분 수열 3

 

 

 

이전에 풀었던 가장 긴 증가하는 부분 수열 3을 확장한 문제이다.

이전 LIS문제에서는 LIS의 길이만 구하는 거였다면, 이번에는 그 수열이 뭔지를 구해야 하는 문제이다.

bisect_left를 통해 LIS배열을 갱신하는 부분은 이전과 동일하고, 해당 수열의 이전값을 추적하기 위한 prev배열을 추가하였다.

또한 prev값 외에도 LIS배열에 그 값이 수열의 어디에서 왔는지도 lis_index 배열에 저장을 해두어야 한다.

lis_index 배열은 LIS 배열에 값이 추가되거나 교체되면, 교체된 값의 인덱스를 같이 갱신해줘야 한다.

 

 

LIS(가장 긴 증가하는 부분 수열), python

LIS(가장 긴 증가하는 부분 수열), python

 

 

수열에서 넣으려는 값	LIS 배열	lis_index 배열	prev 배열	설명
10	[10]	[0]	[-1,-1,-1,-1,-1,-1]	10은 원본수열 0번째 에서왔다. lis_index에 0을 추가한다. 처음값은 prev를 갱신할 필요가없다
20	[10,20]	[0,1]	[-1,0,-1,-1,-1,-1]	20은 원본 수열의 1번째에서왔다. lis_index에 1을 추가한다. prev는 lis_index배열에서 LIS에서 20이 추가된 인덱스(빨간색)의 이전이므로 0(파란색)으로 갱신해준다.
10	[10,20]	[2,1]	[-1,0,-1,-1,-1,-1]	10은 원본수열 2번째에서 왔고, LIS배열이 갱신된 위치에 lis_index도 같이 갱신해준다. 첫번째 값이므로 prev갱신은 하지않는다.
30	[10,20,30]	[2,1,3]	[-1,0,-1,1,-1,-1]	30은 원본수열 3번째에서 왔고, LIS배열에 추가되면서 lis_index배열에도 같이 추가해준다. prev는 lis_index배열에서 LIS에서 30이 추가된 인덱스(빨간색)의 이전이므로 1(파란색)로 갱신해준다
20	[10,20,30]	[2,4,3]	[-1,0,-1,1,2,-1]	20은 원본수열 4번째에서 왔고, LIS배열이 갱신된 위치에 lis_index도 같이 갱신해준다.  prev는 lis_index배열에서 LIS에서 20이 추가된 인덱스(빨간색)의 이전이므로 2(파란색)로 갱신해준다
50	[10,20,30,50]	[2,4,3,5]	[-1,0,-1,1,2,3]	50은 원본수열 5번째에서 왔고, LIS배열이 갱신된 위치에 lis_index도 같이 갱신해준다.  prev는 lis_index배열에서 LIS에서 50이 추가된 인덱스(빨간색)의 이전이므로 3(파란색)로 갱신해준다

 

lis_index 배열은 LIS배열에 해당하는 값이 원본 수열의 어디 인덱스에서 왔는지를 저장하고

prev배열은 LIS배열에 추가되거나 갱신될 때, lis_index에서 이전 인덱스를 저장한다.

값이 갱신될때 갱신된 값의 인덱스를 추적하고, prev를 갱신하는 과정이 이해하는데 시간이 많이 걸렸던 문제이다.

 

from bisect import bisect_left

n = int(input())
arr = list(map(int,input().split()))

lis = []
lis_index = []
prev = [-1]*n

for i in range(n):
    x = arr[i]
    pos = bisect_left(lis,x)

    # LIS 배열이 비었거나 끝에 추가할때
    if pos>=len(lis):
        lis.append(x)
        lis_index.append(i) # 인덱스도 같이 저장

    # LIS 배열에서 교체될때
    else:
        lis[pos] = x
        lis_index[pos] = i # 인덱스도 갱신
    
    # 저장해둔 인덱스 배열에서 이전 인덱스를 prev에 저장
    if pos>0:
        prev[i] = lis_index[pos-1] 
    print(lis_index,prev)

print(len(lis))

result = []
t = lis_index[-1]
# LIS의 마지막 인덱스부터 역추적
while t != -1:
    result.append(arr[t])
    t = prev[t]

answer = ' '.join(map(str,result[::-1]))
    
print(answer)