배달의 민족 배달 가능 여부

[문제]

배달의 민족 서버 개발자로 입사했다.

상점에서 현재 가능한 메뉴가

["떡볶이", "만두", "오뎅", "사이다", "콜라"] 일 때,

유저가 ["오뎅", "콜라", "만두"] 를 주문했다.

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

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)

 

---

 

방법 1)

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

이진 탐색을 통해 메뉴 찾는 속도를 빠르게 만들었고, 각 주문마다 반복해서 찾는다

def is_available_to_order(menus, orders):
    menus.sort()
    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
    count = 0
    while current_min <= current_max:
        current_guess = (current_min + current_max) // 2
        if array[current_guess] == target:
            return True
        elif array[current_guess] < target:
            current_min = current_guess + 1
        else:
            current_max = current_guess - 1
    return False

[시간복잡도]

menus 를 정렬

menus 의 길이를 N 이라고 한다면 O(N * log N) 의 연산이 필요

정렬된 menus 내에서 이진 탐색의 시간 복잡도는 O(log N)

이걸 orders의 개수 M 만큼 반복하게 되므로 O(M * logN) 의 연산 필요

결론) O((M+N)*logn) 만큼의 시간 복잡도가 소요

 

---

 

방법 2)

이 문제는 단순히 특정한 문자열이 배열에 존재하는지만 확인하면 됨

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

* 집합은 중복을 허용하지 않는 자료형

def is_available_to_order(menus, orders):
    menus_set = set(menus)            # O(N)
    for order in orders:              # M번 반복
        if order not in menus_set:    # O(1)
            return False
    return True

[시간복잡도]

menus 를 menus_set 으로 만들기 위해서는 orders 의 길이를 N 이라고 한다면 O(N) 의 연산 필요

집합 내에서 탐색의 시간 복잡도는 O(1) 

이걸 주문의 개수 M 만큼 반복하게 되므로 O(M) 의 연산이 필요

결론) O(M+N) 만큼의 시간 복잡도가 소요

 

 

 

알고리즘에서는 무조건 효율적인 방법이 없습니다!

상황에 따라서 이진 탐색이 효율적일 수도 있고 다른 자료구조를 사용하는 경우가 있다는 것을 느끼셨으면 좋겠습니다!