배달의 민족 문제에서 효율적인 탐색 방법에 대해 질문드립니다

해당강의 : 2주차;2-10. 2주차 끝&숙제 설명

강사님 안녕하세요.

강의 중 두 번째 문제인 ‘배달의 민족 - 배달 가능 여부’ 문제를 풀이하며,
아래와 같이 코드를 작성해보았습니다.

def is_available_to_order(menus, orders):
    for order in orders:
        if order not in menus:
            return "주문 불가능"
    return "주문 가능"

강의에서 설명하신 set()을 활용한 방식이 탐색 효율이 높다는 점은 잘 이해했습니다.
이에 대해 생각해보며, 제가 작성한 방식도 리스트 탐색만으로 충분히 동작하여
데이터 규모가 크지 않은 상황에서는 큰 성능 차이가 없을 것 같다는 생각이 들었습니다.

두 방식 모두 평균적인 입력 크기에서는 큰 차이가 없을 것 같은데,
혹시 제가 사용한 방법도 일정 규모 이하의 데이터에서는 효율적인 접근으로 볼 수 있을지 궁금합니다.
또한, 실제 서비스 코드에서는 어떤 기준으로 set() 변환을 적용하는 것이 바람직한지 알고 싶습니다.

하늘소녀님 좋은 질문 감사합니다!! "언제 어떤 방식을 써야 하나"를 고민하는 게 바로 좋은 개발자가 되는 과정입니다

1. 시간복잡도 차이 - 숫자로 보면 확실해요

작성하신 방식은 order not in menus에서 리스트를 직접 탐색하는 거예요. 파이썬 내부적으로 리스트의 in 연산은 O(N)이에요. 반면 set의 in 연산은 O(1)입니다.

구체적으로 보면, 메뉴가 5개이고 주문이 3개일 때 여러분 방식은 최악의 경우 5 × 3 = 15번 비교해요. set을 쓰면 5번(set 변환) + 3번(검색) = 8번이고요. 이 정도면 차이가 거의 안 느껴집니다.

그런데 메뉴가 1,000개이고 주문이 100개라면? 여러분 방식은 100,000번 비교하는데, set 방식은 1,100번만 하면 돼요. 거의 100배 차이가 나죠. 메뉴 10,000개에 주문 1,000개면? 10,000,000번 vs 11,000번으로 거의 1,000배 차이입니다

2. 현실적인 기준 - 이렇게 판단하세요

데이터가 10개 이하면 솔직히 아무거나 써도 됩니다. 사람이 체감할 만큼의 차이가 안 나거든요. 10~100개 정도면 여러분 방식도 괜찮아요. 밀리초 단위 차이라서 대부분 상황에서 문제없어요.

그런데 100개 이상부터는 set을 쓰는 게 좋아요. 특히 검색을 여러 번 반복한다면요. 1,000개 이상이면 무조건 set이나 다른 효율적인 자료구조를 써야 해요.

중요한 건 "몇 번 검색하느냐"예요. 한 번만 검색한다면 리스트든 set이든 큰 차이 없어요. 그런데 반복문 안에서 계속 검색한다면, 검색 횟수만큼 시간복잡도 차이가 곱해지거든요. 이 문제처럼 주문마다 메뉴를 검색하는 상황이면 set이 훨씬 유리해요.

3. 실제 서비스 코드에서는

실무에서는 이렇게 판단해요. 먼저 데이터 규모의 최댓값을 봐요. "현재는 100개지만 나중에 10,000개가 될 수 있나?" 이런 질문을 던지는 거죠. 확장 가능성이 있으면 처음부터 효율적으로 짜는 게 맞습니다 (근데 또 코드 리뷰 관점에서는 확장 가능성이 없더라도 간단한 코드면 최대한 효율적인게 보기 좋습니다 ㅎㅎㅎ)

그다음엔 얼마나 자주 실행되는 코드인지 봐요. 1분에 한 번 실행되는 배치 작업이면 좀 느려도 괜찮아요. 그런데 사용자가 버튼 누를 때마다 실행되는 API라면? 0.1초 차이도 중요하거든요.

배달의민족 같은 실제 서비스에서 메뉴 검색은 정말 자주 일어나요. 사용자가 주문할 때마다, 장바구니 담을 때마다 검색하니까요. 그래서 처음부터 set이나 해시맵을 쓰는 게 정석이에요.

이렇게 "왜 이 방식이 더 좋은지" 고민하는 자세가 정말 훌륭해요. 계속 이런 식으로 생각하면서 코드를 짜다 보면, 어느 순간 상황에 따라 최적의 자료구조를 자연스럽게 선택하게 될 거예요!

인프런 커뮤니티 질문&답변