[Python] 12015 - 가장 긴 증가하는 부분 수열 2 (골드2)

1. 문제 설명

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

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

[참고]

[Python] 11053 - 가장 긴 증가하는 부분 수열 (실버2)

 

이건 다른 블로그를 참고했었다. 풀이 방법이 굉장히 신기한 문제다.

https://jainn.tistory.com/90

최장 증가 부분 수열(LIS) 알고리즘

 

---

2. 아이디어

수열의 길이가 1,000,000이기 때문에 이전에 사용했던 방법\(O(N^{2})\)을 쓰면 바로 시간초과가 난다.

여기선 최장 증가 부분 수열(LIS, Longest Increasing Subsequence) 알고리즘을 사용해서 해결할 수 있다.

 

입력받은 수열을 차례대로 읽으면서 lis 배열의 가장 마지막 값과 새로 입력받은 값을 비교하여

새로 입력받은 값이 더 크다면 lis에 append한다.

그렇지 않을 경우 lis 배열을 분할 탐색하여 현재 값이 들어갈 수 있는 위치를 찾는다.

"아니, 그러면 순서가 흐트러지잖아요?? "상관없다. 이 문제에서 필요한 건 증가수열의 길이였지

수열을 출력하는 것이 아니다.

 

로직 자체는 굉장히 단순하다.

새로운 값이 들어오는데 증가수열이면 그냥 뒤에 붙이고, 그게 아니면 얘가 들어갈 수 있는 최적의 자리를

새로 만드는 것이 아닌, 기존의 값을 대체 시키게 만드는 것. (없으면 패스)

정말 탐색에만 모든 걸 올인한 미친 알고리즘이 아닐까. 이런 걸 생각해내는 게 너무 존경스럽다.

 

---

3. 코드

import sys

input = sys.stdin.readline

def solution():
    n = int(input())
    a = list(map(int, input().split()))
    lis = [0]

    for current in a: # O(n)
        if lis[-1] < current:
            lis.append(current)
        else: # lis 값 갱신
            left = 0
            right = len(lis)

            while left < right: # O(log n) : 분할 탐색
                mid = (left + right) // 2

                if lis[mid] < current:
                    left = mid + 1
                else:
                    right = mid
            lis[right] = current
    print(len(lis) - 1)


solution()