181. 12015(가장 긴 증가하는 부분 수열2) - 파이썬

본 코드는 PyPy로 제출해야 합니다.

import sys
input = sys.stdin.readline

N = int(input())
A = list(map(int, input().split()))
LIS = []
LIS.append(A[0])

for i in range(1, len(A)):
    if(A[i] > LIS[-1]):
        LIS.append(A[i])

    else:
        start = 0
        end = len(LIS)
        while(end - start >= 0):
            mid = (start + end) // 2

            if(LIS[mid] < A[i]):
                start = mid + 1
            else:
                end = mid - 1
        LIS[start] = A[i]

print(len(LIS))

문제요약

이분 탐색을 이용하여 가장 긴 수열의 길이를 찾아라.

설명

예시를 들어보자.

입력값이 10, 20, 30, 15, 20, 30, 50, 40, 45, 60 이라고 해보자.

여기서 가장 긴 수열은 10, 15, 20, 30, 40, 45, 60이다.

 

나온결과를 표로 정리해보면 아래와 같다.

LIS	탐색값	추가/대치	결과
{10}	20	추가	{10, 20}
{10, 20}	30	추가	{10, 20, 30}
{10, 20, 30}	15	대치	{10, 15, 30}
{10, 15, 30}	20	대치	{10, 15, 20}
{10, 15, 20}	30	추가	{10, 15, 20, 30}
{10, 15, 20, 30}	50	추가	{10, 15, 20, 30, 50}
{10, 15, 20, 30, 50}	40	대치	{10, 15, 20, 30, 40}
{10, 15, 20, 30, 40}	45	추가	{10, 15, 20, 30, 40, 45}
{10, 15, 20, 30, 40, 45}	60	추가	{10, 15, 20, 30, 40, 45, 60}

자 그러면 이분탐색을 어디서 사용하는지에 대한 의문이 들 것이다.

 

이분탐색은 대치에 사용된다!

일단 이 예제에서는 우연히 LIS의 값이 올바르게 나왔다.

하지만 예를 들어 10, 20, 30, 15 가 입력으로 들어 왔을 경우 답은 10, 20, 30 이지만 위 방식은 10, 15, 30 을 출력할 것이다.

 

이 문제는 출력이 아닌 길이를 출력하고자 하는 것이기 때문에 길이 한정으로 이분탐색을 활용할 수 있는 것이다.

(시간을 줄이기 위해서)

 

    if(A[i] > LIS[-1]):
        LIS.append(A[i])

LIS의 끝 값과 현재 탐색값과 비교하고 만약 탐색값이 크다면 추가를 진행한다.

 

    else:
        start = 0
        end = len(LIS)
        while(end - start >= 0):
            mid = (start + end) // 2

            if(LIS[mid] < A[i]):
                start = mid + 1
            else:
                end = mid - 1
        LIS[start] = A[i]

탐색값이 작을 경우에는 대치를 진행하는데 대치 과정에서 이분탐색이 사용된다.

start, end는 인덱스로 사용할 것이다.

때문에 start는 0으로 end는 현재 LIS의 길이로 설정한다.

 

이분탐색으로 비교후 탐색값과 LIS의 값의 차이가 가장 적은 곳을 탐색값으로 대치를 시킨다.