[PS] 메뉴 리뉴얼

문제 링크

코드

def solution(orders, course):
    answer = []
    dishes_sets = [{d for d in o} for o in orders]
    
    for c in course:
        max_size = 0
        max_cases = []
        memory = {}
        
        for o in orders:
            sorted_order = sorted(o)
            
            def create_all_cases(order, count):
                result = []
                
                
                def recursive(picked, idx):
                    if len(picked) == count:
                        result.append(picked)
                        return
                    
                    if idx >= len(order):
                        return
                    
                    recursive(picked + order[idx], idx + 1)
                    recursive(picked, idx + 1)                        
                        
                        
                recursive("", 0)
                return result
            
            
            cases = create_all_cases(sorted_order, c)
            for case in cases:
                if case not in memory:
                    count = len(list(filter(lambda x: {c for c in case} <= x, dishes_sets)))
                    memory[case] = count
                    if max_size < count:
                        max_size = count
                        max_cases = [case]
                    elif max_size == count:
                        max_cases.append(case)
    
        if max_size > 1:
            answer += max_cases
    
    return sorted(answer)

리뷰

collections와 itertools를 이용하면 아래의 풀이와 같이 정말 간단하게 풀 수 있다. 하지만 라이브러리를 몰라도 구현으로 충분히 풀 수 있는 문제고 모든 라이브러리를 다 알 수는 없기 때문에 내가 푼 풀이도 나쁘지는 않다고 생각한다. 다만 collections와 itertools는 많이 활용되는 라이브러리이기 때문에 시간 내어 자주 쓰는 함수들을 정리하면 좋겠다.
그것보다 시간복잡도를 통해 완전 탐색 문제라는 것을 빠르게 알아차리지 못하고 다른 방법을 생각하기 위해서 고민했던 것이 아쉽다. 시간복잡도를 어림하는 것을 더 연습해야겠다.

import collections
import itertools

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

    for course_size in course:
        order_combinations = []
        for order in orders:
            order_combinations += itertools.combinations(sorted(order), course_size)

        most_ordered = collections.Counter(order_combinations).most_common()
        result += [ k for k, v in most_ordered if v > 1 and v == most_ordered[0][1] ]

    return [ ''.join(v) for v in sorted(result) ]

풀이 링크