[프로그래머스] 메뉴 리뉴얼

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

프로그래머스

 

1. 문제설명

• 단품 메뉴들을 조합해서 코스요리 형태로 재구성하기
• 메뉴 주문시 가장 많이 함께 주문한 단품메뉴들을 선택
• 단, 최소 2가지 이상의 단품메뉴로 구성 / 최소 2명 이상의 손님으로부터 주문된 것 단품메뉴 조합에 대해서만 후보에 포함

 

 

2. 코드구현

def solution(orders, course):
    # 'XA'와 'AX'가 다르게 카운트 되는 것 방지 
    for i in range(len(orders)):
        orders[i] = ''.join(sorted(list(orders[i])))
    
    def make_combi(orders, n):
        combi = []
        def backtrack(order, cur, cur_i, n):
            # base case
            if len(cur) == n:
                combi.append(''.join(cur))
                return
            # repeat
            for i in range(cur_i, len(order)):
                cur.append(order[i])
                backtrack(order, cur, i+1, n)
                cur.pop()
            
        for order in orders:
            backtrack(order, [], 0, n)
        return combi
    
    result = []
    # 코스 종류에 대해 각각 처리 
    for n in course:
        max_n = 0 # 딕셔너리에서 value의 최대 개수를 구하기 번거롭고, 최대값을 가지는 여러개의 key가 있을 수 있기 때문에 변수로 비교
        combi = make_combi(orders, n) # 길이n을 가진 조합 찾기
        dict = {}
        for f in combi: # 만들어진 조합 돌면서 딕셔너리에 개수 저장 
            if f not in dict:
                dict[f] = 1
            else:
                dict[f] += 1
            max_n = max(max_n, dict[f]) # key에 대한 최댓값 갱신
        # 딕셔너리에 모두 저장했으면 저장된 최댓값을 가지는 key 구하기 & 2개 이상이어야 하는 문제 조건
        for k, v in dict.items():
            if v >= 2 and v == max_n:
                result.append(k)
    result.sort()
    return result

 

 

3. 주의사항

• 입력 받은 대로 실행하면 [’A’, ‘B’]와 [’B’, ‘A’]는 같은 메뉴 구성인데 다르게 될 수도 있다. → sort
• combination을 만드는 backtrack 함수에서 범위 주의하자 i의 범위는 (cur_i ~ len(order))이고 i+1을 넣어주어야 함