[백준] 가장 긴 증가하는 부분 수열 2 12015번 (python)

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

 

풀이 방법

LIS 알고리즘 중 binary search를 이용한 방법으로 풀이하면 된다. 

LIS의 binary search가 기존의 binary search와 다른 점은 기존의 binary search는 특정 값을 찾아야 하지만 LIS에서의 binary search는 특정 값을 찾는 거뿐만 아니라 찾아야 하는 값이 없다면 자신보다 작은 수 중에 가장 큰 수의 인덱스에 +1 한 인덱스를 찾아주어야 한다. 

 

def binary(num): 
    left = 0
    right = len(temp)-1   
    mid = 0 
    while (left <= right):        
        mid = (left + right) // 2
        if num == temp[mid]: return mid
        elif temp[mid-1] < num < temp[mid]:
            return mid
        elif num < temp[mid]:        
            right = mid - 1
        else:
            left = mid + 1        
    return mid

 

위의 binary search 코드처럼 해당 값이 존재한다면 해당 값의 idx를 반환하고 만약 해당 값이 존재하지 않고 해당 값이 어떤 두 수의 사이에 있다면 그때의 mid의 값을 반환한다. 

 

LIS함수는 temp의 마지막 값보다 다음 arr의 값이 크다면 temp 배열의 뒤에 해당 원소를 추가해 주고 

그렇지 않다면 binary search를 통해 temp배열에 넣어줄 idx를 찾아 해당 값을 넣어준다.

temp의 초기 값은 arr[0]의 값으로 설정하고 1~N-1까지 순회하며 처리해 준다.

 

def LIS():
    ans = 0
    for i in range(1, N):
        target = arr[i]
        if temp[-1] < target: ## 마지막 수보다 크면 배열에 추가하기
            temp.append(target)
        idx = binary(target) 
        temp[idx] = target          
    return len(temp)

 

전체 코드

N = int(input())
arr = list(map(int, input().split()))
temp = [arr[0]]
def binary(num): 
    left = 0
    right = len(temp)-1   
    mid = 0 
    while (left <= right):        
        mid = (left + right) // 2
        if num == temp[mid]: return mid
        elif temp[mid-1] < num < temp[mid]:
            return mid
        elif num < temp[mid]:        
            right = mid - 1
        else:
            left = mid + 1        
    return mid
    
def LIS():
    ans = 0
    for i in range(1, N):
        target = arr[i]
        if temp[-1] < target: ## 마지막 수보다 크면 배열에 추가하기
            temp.append(target)
        idx = binary(target) 
        temp[idx] = target          
    return len(temp)
   
print(LIS())