알고리즘/프로그래머스
-
메뉴 리뉴얼알고리즘/프로그래머스 2021. 5. 29. 18:09
문제 푸는 키 포인트는 두개다. 1. 손님들마다 주문한 단품 메뉴 목록에서 가능한 조합을 목록으로 만든다. 손님이 최대 주문 할 수 있는 단품 메뉴의 개수가 10개다. 그러면 10개로 만들 수 있는 조합의 개수는 2^10 - 1개. 알고리즘 시험 문제에서 풀 수 있을 만큼의 범위다. 단품의 개수가 2개 이상인 조합만 고려대상이지만 이건 일단 무시하도록 하자. 코딩으로 조합 목록을 만드는 방법은 다양하게 있을텐데 내 경우에는 비트마스크를 사용했다. 만약 손님이 5개를 주문 했다면 총 31가지 조합이 만들어지므로, 1 ~ 31 까지 For 루프를 돌고 각 회차별로 비트를 확인 해서 단품 목록을 포함 시킬 것인지 말 것인지를 결정한다. for (int i = 0; i < orders.size(); i++) {..