[Python] 백준 12015번: 가장 긴 증가하는 부분 수열 2

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

12015번: 가장 긴 증가하는 부분 수열 2

 

import sys
import bisect
input = sys.stdin.readline

if __name__ == '__main__':
    N = int(input())
    nums = list(map(int, input().split()))

    stack = []
    for n in nums:
        minBiggerIndex = bisect.bisect_left(stack, n)

        if minBiggerIndex == len(stack):
            stack.append(n)
        else:
            stack[minBiggerIndex] = n

    print(len(stack))

 

먼저 시간 조건부터 확인한다. 크기가 1,000,000이고 시간 제한이 1초이므로, 이 문제는 O(NlogN) 안에 풀어야한다는 것을 알 수 있다.

LIS(Longest Increasing Subsequence)의 길이 구하기는, 쉽게 생각할 수 있는 O(N^2) 풀이와 어려운 O(NlogN) 풀이가 있으며, 후자의 방법으로 이 문제를 푼다.

 

우리는 이 문제를 풀기 위해 하나의 빈 스택을 준비한다. 이 곳에는 증가하는 숫자들을 계속해서 추가해나갈 것이다. 주의할 점이 있는데, 이곳에는 최종적으로 가장 긴 증가하는 부분 수열이 저장되는 것이 아니라, 그 수열과 길이만 같은, 인덱스의 순서가 뒤죽박죽인 증가하는 수열이 저장된다는 것이다.

 

우선, 입력받은 모든 숫자에 대해 반복문을 돌려준다.

 

다음으로, 반복문의 현재값을 n이라고 했을 때, bisect.bisect_left(stack, n)을 해준다. 즉, n 이상인 값들 중에 가장 작은 곳의 인덱스를 가져와준다. 만약 [10, 20, 30]에서 15를 검색하면 20이 나온다. 그리고 40을 검색하면 3이 나오게 되는데, 검색 결과가 리스트의 길이와 같다면 검색값이 그 리스트의 모든 값보다 크다는 뜻이다. 이것을 이용하여, 'n이 stack의 모든 값보다 클 때'와 '아닐 때'를 구분지을 수 있다.

만약 전자의 경우라면, n을 추가해준다. 만약 스택이 [10, 20]일 때 n이 30이라면, [10, 20, 30]으로 만들어준다는 것이다.

후자의 경우일 경우에는, 검색된 인덱스의 값을 n으로 교체해준다. 만약 [10, 20, 30]일 때 n이 15라면, [10, 15, 30]이 된다.

 

마지막으로 stack의 길이를 출력해주면 된다.