백준 / 가장 긴 감소하는 부분 수열 / 11722번 / Python

*문제 출처는 백준에 있습니다.

문제 제목: 가장 긴 감소하는 부분 수열 / 11722번 (실버 2단계)

문제 사이트: https://www.acmicpc.net/problem/11722

 

문제 설명

---

나의 풀이

def solution(arr):
    arr_len = len(arr)

    result = [1001]

    for i in range(arr_len):
        current = arr[i]

        # 현재 값이 result의 마지막 값보다 크면 그대로 추가
        if current < result[-1]:
            result.append(current)
        else:
            # 이분 탐색으로 교체할 위치 찾기
            left = 0
            right = len(result) - 1

            while left < right:
                mid = (left + right) // 2
                if result[mid] > current:
                    left = mid + 1
                else:
                    right = mid

            result[left] = current  # 알맞은 위치에 값 교체

    print(len(result) - 1)  # 첫 dummy 값(1001)을 제외한 길이


def main():
    n = int(input())
    arr = list(map(int, input().split()))
    solution(arr)


if __name__ == "__main__":
    main()

---

※ 알아야 할 것

def solution(arr):
    arr_len = len(arr)

    result = [1001]

    for i in range(arr_len):
        # 현재의 변수
        current = arr[i]

        # 더 작으면 그냥 넣기
        if current < result[-1]:
            result.append(current)
        else:
            left = 0
            right = len(result)
            # 중앙
            center = (left + right) // 2

            while left < right:
                # 30 > 20
                if result[center] > current:
                    left += 1
                    center = (left + right) // 2
                else:
                    right = center - 1
            # 자기 위치 
            result[center] = current

위 풀이는 이분탐색의 잘못된 예입니다!

left += 1 증가 시키는 경우 최악의 경우 n^2의 시간 복잡도가 발생할 수 있습니다.