[프로그래머스][구현][완전 탐색] 메뉴 리뉴얼

메뉴 리뉴얼

프로그래머스

 

• 내 풀이
  • 완탐 + 구현
  • 각 주문을 정렬한 후에, 가능한 모든 조합 생성
    • → XYZ나 YXZ나 똑같이 {XY, XZ,YZ} 조합으로 뽑기 위함
  • 생성된 조합들의 등장 횟수를 Counter를 이용해 계산
  • 필터링:
    • 최소 2번 이상 등장한 조합만 고려
    • course에 포함된 길이(메뉴 개수)만 선택
    • 같은 길이의 조합 중 가장 많이 등장한 조합 저장
  • 선택된 메뉴 조합을 사전순으로 정렬하여 반환

from collections import Counter, defaultdict
from itertools import combinations
def solution(orders, course):
    results = defaultdict(list)
    combi=[]
    course=set(course)

    for order in orders:
        order=sorted(list(order))
        for i in range(2,len(order)+1):
            combi+=list(combinations(order,i))
    cnt_combi=Counter(combi)
    
    for key,val in sorted(list(cnt_combi.items()), key=lambda x:x[1], reverse=True):
        #최소 2번이상의 조합
        if val<2:
            continue
            
        n= len(key)
        # course에 속한 길이만
        if n in course:
            if not results[n]:
                results[n]=[(''.join(key), val)]
                continue
            if results[n][0][1]<=val:
                results[n].append((''.join(key), val))

    answer=[]
    for result in list(results.values()):
        for r in result:
            answer.append(r[0])
    return sorted(answer)

 

• 다른 사람 풀이
  • course 갯수 조합 한번에 다 안넣고 하나하나 따로 확인

from collections import Counter
from itertools import combinations

def solution(orders, course):
    result = []

    for course_size in course:
        order_combinations = []
        for order in orders:
            order_combinations += combinations(sorted(order), course_size)
        
        most_ordered = Counter(order_combinations).most_common()
        
        # 최다 주문 횟수 확인 (2회 이상 등장한 경우만 고려)
        max_count = most_ordered[0][1] if most_ordered and most_ordered[0][1] > 1 else 0
        
        # 최다 주문 횟수와 동일한 조합만 결과에 추가
        for k, v in most_ordered:
            if v == max_count:
                result.append(k)
    
    return [''.join(v) for v in sorted(result)]