[프로그래머스][2021 KAKAO BLIND RECRUITMENT][Python] 메뉴 리뉴얼

문제를 정리해보자.

 

이전에 각 손님이 주문할 때 가장 많이 함께 주문했던 단품 메뉴들을 코스요리 메뉴로 구성한다.

 

1) 코스요리 메뉴는 최소 2가지 이상의 단품 메뉴로 구성된다.

2) 최소 2명 이상의 손님으로부터 주문된 단품 메뉴 조합에 대해서만 코스요리 메뉴 후보에 포함한다.

 

---

 

입출력

 

1. orders: 각 손님이 주문한 단품 메뉴들이 문자열 형식으로 담긴 배열 

2. course: "스카피"가 추가하고 싶어하는 코스요리를 구성하는 단품 메뉴들의 개수가 담긴 배열

 

 

https://programmers.co.kr/learn/courses/30/lessons/72411

 

 

---

 

풀이를 생각해보자.

 

첫 번째 예로 생각해보자.

 

 

 

 

 

 

ABCFG로 만들 수 있는 2, 3, 4개 코스의 후보는 아래와 같다.

 

 

 

 

 

 

이렇게 orders의 메뉴 구성마다 N개 코스의 후보를 구한다.

 

최종적으로 N개 코스마다 가장 많이 주문된 후보가 정답이다.

다만, 가장 많이 주문된 횟수가 1개일 경우는 정답이 아니다.

(최소 2명 이상의 손님에게서 주문된 구성만 코스요리 후보에 들어가기 때문이다.)

 

 

---

 

​구현해보자

 

아래순서로 구현했다.

 

1. 2개 코스 -> 이 코스에서 가장 많이 주문된 후보 탐색

2. 3개 코스 -> 이 코스에서 가장 많이 주문된 후보 탐색

3. 4개 코스 -> 이 코스에서 가장 많이 주문된 후보 탐색

 

​주문한 단품 메뉴 조합마다 N개코스의 조합을 만드는 것은 백트래킹을 이용했다.

 

 

from collections import defaultdict


def back(order, n, m, li, dp, check, cnt):
    if cnt == m:
        check[''.join(li)] += 1
        return

    for i in range(0, n):
        if li and (dp[order[i]] == 1 or order[i] < li[-1]):  # 중복방지 예) ABC, CBA
            continue

        li.append(order[i])
        dp[order[i]] = 1

        back(order, n, m, li, dp, check, cnt + 1)

        dp[li[-1]] = 0
        li.pop()


def solution(orders, course):
    dp = defaultdict(int)
    check = defaultdict(int)

    answer = []

    for m in course:
        for order in orders:
            n = len(order)
            li = []

            back(order, n, m, li, dp, check, 0)
        
        # 최대 주문 조합 탐색
        idx_li = sorted(check.values())
        for key in check:
            if check[key] != 1 and check[key] == idx_li[-1]:  # 최소 2명 이상 손님
                answer.append(key)

        check = defaultdict(int)

    return sorted(answer)


solution(["ABCFG", "AC", "CDE", "ACDE", "BCFG", "ACDEH"], [2, 3, 4])