(Python/🥇2)백준알고리즘 12015번: 가장 긴 증가하는 부분 수열2

 

문제 바로가기 

문제:

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

출력:

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

 

 

핵심은, 수열 A를 처음부터 끝까지 for를 돌면서  LIS를 만드는데, LIS의 원소들은 A의 "가장 긴 증가하는 부분 수열"을 만족하지는 않지만, 이 리스트 LIS의 길이 값 자체만은 A의 "가장 긴 증가하는 부분 수열" 조건을 만족한다는 것을 이해하는 것이다.

예를들면 

 

6
10 20 10 30 40 10 12 14

일 경우 돌려보면 마지막에 이렇게 값이된다. [10, 12, 14, 40]

가장 긴 증가하는 부분 수열은 아니지만 이전에 [10,20,30,40] 으로 길이 4가 만들어졌기때문에 4로 된다. 만약 뒤에 16 18 이 있다면

[10, 12, 14, 16,18] 이렇게 바뀌어서 5개가 정답일 될 것이다.

 

풀이:

import sys
from bisect import bisect_left

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

N = int(sys.stdin.readline())
lst = [int(i) for i in sys.stdin.readline().split(" ")]

# 시간 초과 코드
# dp = [1] * N
# for i in range(N):
#     for j in range(i):
#         if lst[i] > lst[j]:
#             dp[i] = max(dp[i], dp[j] + 1)
# print(max(dp))

stack = []
for i in lst:
    if not stack or stack[-1] < i:
        stack.append(i)
    else:
        x = bisect_left(stack,i)
        stack[x] = i
print(len(stack))

bisect_left 는 정렬된 list (stack) 에 넣을 i에 좌표를 알려 준다.

6
10 20 10 30 40 10 15 20 25 30

이걸로 예시를 들어보겠다.

처음엔 10이 들어가고

그다음 20은 10보다 크니깐 [10,20] 이렇게 들어간다

그 다음은 stack에 마지막 원소인 20 보다 크지 않으니깐 stack에  들어가지 않고 10이 들어갈 인덱스를 찾아 들어간다

그러면 

10 20

이렇게 10이 있는 위치에 그대로 10이 들어가고

그 다음인 30 40 은 뒤로 쭊쭊 들어간다

10 20 30 40

그리고 15가 나오게 된다. 15는 이분탐색으로 들어갈 위치를 찾는데 그 위치는 20인 위치이다. 그래서 20 대신에 15가 들어간다

10 15 30 40

그 다음원소인 20 25 똑같다

[10, 15, 20, 25]

여기 까지 오게되고 아직 남은 원소 30은 들어갈 수 있게 되므로

[10, 15, 20, 25, 30]

정답은 고로 5 이다.

 

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 최장증가수열