알고리즘 with python.04

배달의 민족 배달 가능 여부

order 받은 요소들이 menu 에 있는지 확인하는 코드 입니다.

True값을 반환한다면 달이 가능하다는 것입니다.

 

1번째 코드

이분탐색으로 요소들을 추측탐색하여 결과를 찾습니다.

tip. 이분탐색을 위한 전제 조건은 정렬이며, 파이썬에서는 .sort()함수를 이용해 간단하게 정렬이 가능하다.

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


def is_available_to_order(menus, orders):
    shop_menus.sort()
    for order in orders:
        if not is_existing_target_number_binary(order, shop_menus):
            return False

        return True

    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
        else:
            current_max = current_guess - 1
        current_guess = (current_max + current_min) // 2
    return False


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

 

이진탐색이 아닌 다른 방법으로 더욱 간단하게 값을 찾을 방법을 고민해봐야합니다.

다양한 문제에 맞는 다양한 자료구조가 존재하기 때문에 특정 하나의 자료구조가 가장 좋다고 할 수 없는 이유가 됩니다.

2번째 코드

set이라는 집합구조를 이용하여 중복을 자동으로 제거 하였고 때문에 코드가 간소화 되었습니다.

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


def is_available_to_order(menus, orders):
    menus_set = set(menus)  # set은 집합을 의미 한다.
    for order in orders:
        if order not in menus_set:
            return False

    return True


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