[알고리즘] - 현재 주문 가능한 상태 확인/파이썬

문제

Q. 배달의 민족 서버 개발자로 입사했다.
상점에서 현재 가능한 메뉴가 ["떡볶이", "만두", "오뎅", "사이다", "콜라"] 일 때, 유저가 ["오뎅", "콜라", "만두"] 를 주문했다.

그렇다면, 현재 주문 가능한 상태인지 여부를 반환하시오.

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

코드 스니펫

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

def is_available_to_order(menus, orders):
    # 이 부분을 채워보세요!
    return True

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

정답 풀이

첫 번째 방법

배열을 가나다 순으로 정렬한 뒤, 이진 탐색을 사용할 수 있다.

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

def is_available_to_order(menus, orders):
    menus.sort()  # menus 정렬!
    for order in orders:
        if not is_existing_target_number_binary(order, 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
        else:
            current_max = current_guess - 1
        current_guess = (current_min + current_max) // 2

    return False

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

두 번째 방법

정렬을 할 필요없이, 집합 자료형을 사용하면 쉽게 해결할 수 있다.

집합은 중복을 허용하지 않는 자료형이다.

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

def is_available_to_order(menus, orders):
    menus_set = set(menus)
    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)

문제를 풀고 알게 된 개념 및 소감

• 배열 정렬
  • 정렬하고 싶은 배열 뒤에 .sort() 함수 호출
• set
  • 중복을 허용하지 않는 자료형