Python 이분탐색 알고리즘 활용

Python 이분탐색 알고리즘 활용

shop_menus = ["만두", "떡볶이", "오뎅", "사이다", "콜라"]
shop_orders = ["오뎅", "콜라", "만두"]


def is_available_to_order(menus, orders):
    shop_menus.sort() # 정렬

    for order in orders : # order를 orders에서 하나하나 뽑아서 밑에있는 이분탐색 함수를 돌려보면 될 것
        if not is_existing_target_number_binary(order, shop_menus):
        # 하나라도 존재하지 않는다면
            return False
    return True


## 이분탐색의 코드
def is_existing_target_number_binary(target, array):
    current_min = 0
    current_max = len(array) - 1
    current_guess = current_min + current_max // 2  # 소숫점은 필요없기 때문에

    while current_min <= current_max:
        if array[current_guess] == target:
            return True
        elif array[current_guess] < target:
            current_min = current_guess + 1  # 최솟값을 시도값 +1로 변경 / 다운은 최댓값을 시도값 -1로 변경
        else:
            current_max = current_guess - 1

        current_guess = (current_max + current_min) // 2  # 새롭게 current_guess를 업데이트
    return False  # 한번도 발견되지 않았다면 return False


result = is_available_to_order(shop_menus, shop_orders)
print(result)


# 이 함수의 시간 복잡도는
# 정렬의 시간 복잡도는 배열의 길이를 N이라고 한다면,
# O(N * logN)
# 찾는데 걸리는 시간은 O(M * logN)
# 즉 O((M+N) * logN)

주문목록에 있나 없나를 True,False로 반환받고 싶을 때,

이분탐색 코드를 사용하여 판별할 수 있다.

    for order in orders : # order를 orders에서 하나하나 뽑아서 밑에있는 이분탐색 함수를 돌려보면 될 것
        if not is_existing_target_number_binary(order, shop_menus):
        # 하나라도 존재하지 않는다면
            return False
    return True

orders의 범위만큼의 for문을 돌린다. (여기서 orders는 힘수 is_available_to_order의 orders 즉 변수 shop_orders다)

 

반복문이 돌아갈 때 마다 아까 사용한 이분탐색 함수 코드를 돌린다.

 

만약 여기서 하나라도 값이 나온다면 True를 반환해주고, if not에 걸려 존재하지 않는다면 for문을 끊고 False를 반환해준다.

---

 

문제점

 

위 주석처럼 시간복잡도가 O((M+N) * LogN)이기 때문에 굉장히 복잡하다.

 

더 빠르고 간결하게 코드를 개선해야한다.

 

---

Set집합을 활용한 개선

shop_menus = ["만두", "떡볶이", "오뎅", "사이다", "콜라"]
shop_orders = ["오뎅", "콜라", "만두"]



def is_available_to_order(menus, orders):
    menus_set = set(menus) #set은 집합을 의미 O(N)
    for order in orders: #M
        if order not in menus_set: # O(1)
            return False
    return True

result = is_available_to_order(shop_menus, shop_orders)
print(result)

# O(N) + O(M) = O(N+M)
# 이분탐색이 모든 자료에 효율적이지 않다. 경우에 따라 다르다.

중복된 것을 제거해주고, 단순하게 for문을 돌려

만약 order가 set을 활용해 중복을 제거한 menus_set에 존재하지 않다면 False를 반환해주면 되고,

for문이 끝까지 돈다면 True를 반환해주면된다.

 

항상 이분탐색이 효율적이지 않다.