백준: 12015 최장 증가 부분 수열 2

문제

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

 

문제 풀이

 앞서 푼 문제들 중에 이 문제와 유사한 문제들을 다루었다.

 

• 가장 긴 증가하는 부분 수열
• 가장 긴 증가하는 부분 수열 4
• 가장 큰 증가 부분 수열
• 가장 긴 감소하는 부분 수열
• 가장 긴 바이토닉 부분 수열 

 하지만 이 문제는 위의 문제들과 달리, N의 크기가 최대 1,000,000으로 위의 문제를 해결한 방식으로 풀고자 하면 시간 초과가 발생한다. 앞서 다룬 문제들은 시간 복잡도가 O(N^2)이 걸리게 된다. 따라서 순열을 탐색하는 데 있어 시간을 최적화할 수 있는 방안이 필요하다.

 

 최장 증가 부분 수열 문제는 최적화 문제에 대해 이미 잘 알려져 있는 문제이다. 나무위키에도 이와 관련한 설명이 있으며 이를 이해하고 문제를 풀면 쉽게 풀 수 있다.

 

• list를 하나 만들어, 우선 수열의 첫 원소를 삽입한다.
• list의 마지막 원소보다 수열에서 가져온 숫자가 크면 list에 삽입한다.
• 아닐 경우, 리스트 내에 해당 숫자를 삽입할 수 있는 위치를 이진 탐색을 통해 계산한 후 값을 경신한다.

 

코드

from sys import stdin


def search_index(num):
    s, e = 0, len(lis) - 1

    while s < e:
        m = (s + e) // 2
        if lis[m] == num:
            s = e = m
        if lis[m] < num:
            s = m + 1
        elif lis[m] > num:
            e = m
    return s


if __name__ == '__main__':
    n = int(stdin.readline())
    nums = list(map(int, stdin.readline().split()))
    lis = [nums.pop(0)]

    for num in nums:
        if lis[-1] < num:
            lis.append(num)
        else:
            lis[search_index(num)] = num

    print(len(lis))