프로그래머스_메뉴 리뉴얼

문제

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

코딩테스트 연습 - 메뉴 리뉴얼

풀이

check : { "A":1, "AB":1, "AC".:1...}

# A, AB, ABC...의 메뉴조합을 조사하였다.

 

ans : { 2 : [ "AB", "AC"], 3 : [ "ABC" ]... }

# 길이가 2이고 가장 많이 주문한 메뉴조합은 AB, AC가 있다.

# 길이가 3이고 가장 많이 주문한 메뉴조합은 ABC가 있다.

 

max_count : { 2 : 3, 3 : 2...}

# 길이가 2이고 가장 많이 주문한 메뉴조합의 주문횟수는 3번이다.

# 길이가 3이고 가장 많이 주문한 메뉴조합의 주문횟수는 2번이다.

 

1. stack에서 메뉴조합을 꺼낸다.

2. 최소 2명 이상의 손님으로부터 주문되었고

3. 메뉴조합에 속한 메뉴 개수가 course 안에 존재한다면

4. 해당 메뉴조합을 저장한다.

5. 메뉴조합에 메뉴를 하나씩 더해 stack에 저장한다.

 

코드

from collections import defaultdict

def solution(orders, course):
    check = defaultdict(int) # 탐색한 문자열 저장
    ans = defaultdict(list) # 조건에 맞는 문자열 저장
    max_count = defaultdict(int) # 문자열이 주문된 횟수 저장(문자열 별)
    
    alpha = sorted(set([m for o in orders for m in o])) 

    # 깊이 우선 탐색
    stack = [('', 0)]
    while stack :
        combi, index = stack.pop() # combi는 합성한 문자열, index는 합성할 수 있는 문자의 시작 위치
        if check[combi]==1 : continue # 이미 탐색한 노드라면, 넘어가기
            
        size = len(combi)
        count = len([1 for o in orders if set(combi) - set(o) == set()]) # 문자열이 들어있는 주문의 횟수 세기
        check[combi] = 1 # 해당 노드를 탐색하였다.

        if count >= 2 : # 최소 2명 이상의 손님으로부터 주문되었다면,
            if size in course : # 메뉴의 조합이 코스메뉴크기와 같다면,                 
                if count>max_count[size] : 
                    max_count[size] = count # 길이가 size인 문자열이 가장 많이 주문된 횟수는 count번
                    ans[size] = [combi] # 길이가 size인 문자열을 모아 둔 공간 초기화하고 combi추가
                elif count==max_count[size] :
                    ans[size].append(combi) # 길이가 size인 문자열을 모아 둔 공간에 combi추가

        else : combi = combi[:-1] # 가장 오른쪽 문자 제거

        # 문자열 합성
        for i in range(index, len(alpha)):
            if check[combi+alpha[i]] == 1: continue # 이전에 탐색한 문자열이라면 지나가기
            stack.append((combi + alpha[i], i + 1)) # 합성된 문자열과 합성할 수 있는 문자의 시작 위치를 stack에 저장
            
    answer = [item for c in course for item in ans[c]] # ans의 길이가 c인 가장 많이 함께 주문된 메뉴 구성들을 반환
    return sorted(answer)