[백준 14003번] 가장 긴 증가하는 부분 수열 5 (Python3)

import sys
input = sys.stdin.readline
from bisect import bisect_left
INF = sys.maxsize

N = int(input())
seq = [*map(int,input().split())]

DP = [-INF]
LIS = [""]

for num in seq:
  if num > DP[-1]:
    DP.append(num)
    LIS.append(LIS[-1]+" "+str(num))
  else:
    idx = bisect_left(DP,num)
    DP[idx] = num
    LIS[idx] = LIS[idx-1]+" "+str(num)

print(len(DP)-1)
print(LIS[-1].strip())

 

처음에 내가 제출하였던 코드는 이러하다. LCS 2번 문제를 풀었던 경험을 살려서, 가장 긴 증가하는 부분 수열을 각 DP마다 스택으로 쌓아서 저장해주고 이후 출력하였다.

 

그러나 이 코드는 메모리 초과가 발생하였다. 가장 긴 증가하는 부분 수열 4번에 제출해본 결과 성공한 것으로 봐서는 알고리즘이 틀린것은 아니었지만 문제는 스택을 계속 쌓음으로 인해서 발생하는 공간복잡도였다. 

길이가 최대 N인 문자열을 최대 N개만큼 저장하니 공간복잡도가 너무 커지는 것이었다.

 

 

이를 수정한 코드는 다음과 같다.

 

import sys
input = sys.stdin.readline
from bisect import bisect_left
INF = sys.maxsize
sys.setrecursionlimit(10**7)

def printseq(x):
  if x==-1:
    return
  printseq(parent[x])
  print(seq[x],end=" ")

N = int(input())
seq = [*map(int,input().split())]

DP = [-INF]
DPi = [-1]
parent = {}

for i in range(N):
  num = seq[i]
  if num > DP[-1]:
    DP.append(num)
    DPi.append(i)
    parent[i] = DPi[-2]
  else:
    idx = bisect_left(DP,num)
    DP[idx] = num
    DPi[idx] = i
    parent[i] = DPi[idx-1]

print(len(DP)-1)
printseq(DPi[-1])
print()

 

 

전체적인 LIS 길이를 구하는 알고리즘은 가장 긴 증가하는 부분수열 2와 똑같다.

 

부분수열을 스택형식으로 쌓는것이 아닌 좌표만 저장한다. 그리고 해당 좌표에 대해서 이전 좌표를 parent dict를 이용해 저장한다.

그리고 모든 계산이 끝나면 부모노드를 계속 불러오면서 print 해준다.

 

 

이번 문제를 통해서 시간복잡도 뿐만이 아닌 공간복잡도 또한 중요하다는 사실을 알게되었다.

 

 

오늘의 교훈) 공간복잡도를 의식하자