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

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

나의 풀이

N = int(input())
result = [0]
def binary_search(target, start, end):
    while start <= end:
        mid = (start + end) // 2
        if result[mid] < target:
            start = mid + 1
        else:
            end = mid - 1
    return start

subsequence = list(map(int, input().split()))
for i in subsequence:
    if result[-1] < i:
        result.append(i)
    else:
        result[binary_search(i, 0, len(result) - 1)] = i

print(len(result) - 1)

• 순차적인 배열을 담을 result 리스트를 생성하고 처음에 0을 담아둔다. 이 0은 입력되는 정수들과 비교하기 위해 사용된다.
• 이분 탐색은 target(subsequence 리스트의 값)을 result에서 탐색한다.
• start가 end보다 커질 때 까지 반복을 한다.
• mid 값을 구해주고, result의 mid 번 째 값이 타겟보다 작다면 start = mid + 1, 아니면 end = mid - 1 을 해준다.
• 반복이 끝나면 start 인덱스를 반환한다.
• 입력받은 숫자들을 subsequence 배열에 숫자로 변환하여 담아준다.
• subsequence 배열을 돌면서 result의 가장 마지막 인덱스의 정수와 비교하여 subsequence의 값이 더 크면 result에 해당 정수를 추가해준다.
• 아니라면 이분 탐색을 통하여 인덱스를 추출하여 스택의 해당 인덱스의 값을 subsequence의 값으로 세팅 해준다.
• 위 과정을 통해 result의 세팅이 끝나게 되고, 비교를 하기 위해 0을 추가했었기 때문에 result사이즈에서 -1을 해준다.