(Python/플5)백준 알고리즘 14003번: 가장 긴 증가하는 부분 수열

 

문제바로가기 

 

문제:

수열 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,000,000,000 ≤ Ai ≤ 1,000,000,000)

출력:

첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다. 둘째 줄에는 정답이 될 수 있는 가장 긴 증가하는 부분 수열을 출력한다.

 

풀이:

 

시간 초과 코드

import sys

N = int(sys.stdin.readline())
numbers = list(map(int, sys.stdin.readline().rstrip().split(" ")))
dp = [1] * N
for i in range(N):
    for j in range(i):
        if numbers[i] > numbers[j]:
            dp[i] = max(dp[i], dp[j] + 1)
now = max(dp)
res = []
for i in range(N - 1, -1, -1):
    if dp[i] == now:
        res.append(numbers[i])
        now -= 1
print(len(res))
print(*res[::-1])

 

포문이 두번 이기 때문에

N^2 이여서 시간초과가 난다.

 

그래서 

import bisect
import sys


N = int(sys.stdin.readline())
numbers = list(map(int, sys.stdin.readline().rstrip().split(" ")))
res = []
for i in range(N):
    if res != [] :
        if res[-1] <= numbers[i]:
            res.append(numbers[i])
        else:
            idx = bisect.bisect_left(res, numbers[i])
            res[idx] = numbers[i]
    else:
        res.append(numbers[i])
print(len(res))
print(*res)

 

이런식으로 길이가 늘어날때 그 숫자의값을 저장해두는 res를 만들었다.

하지만 res[idx] = numbers[i] 를 추가하면서 데이터가 다 바뀌어버린다.

 

그러면 처음에 넣을때 아예 인덱스 값을 넣기로 했다. 

 

import bisect
import sys

sys.stdin = open('/Users/song/Desktop/Python/Python/h.txt', 'r')

N = int(sys.stdin.readline())
numbers = list(map(int, sys.stdin.readline().rstrip().split(" ")))

dp = [numbers[0]]
res = []
for i in numbers:
    if dp[-1] < i:
        dp.append(i)
        res.append((len(dp) - 1, i))
    else:
        temp = bisect.bisect_left(dp, i)
        dp[temp] = i
        res.append((temp, i))
result = []
index = len(dp) - 1
for i in range(len(res) - 1, -1, -1):
    if res[i][0] == index:
        result.append(res[i][1])
        index -= 1
print(len(dp))
print(*result[::-1])

 

LIS 수열

https://windy7271.tistory.com/entry/LIS-%EC%B5%9C%EC%9E%A5%EC%A6%9D%EA%B0%80%EC%88%98%EC%97%B4

LIS 최장증가수열