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

문제출처 : https://programmers.co.kr/learn/courses/30/lessons/72411

접근법

1. orders 배열에 있는 각 원소들 ( "XYZ" , "WXY" 등 )으로 가능한 모든 조합들을 구한다.

• 처음에 재귀함수를 통해 combination을 구현했는데 ("W","X") , ("X,"W")를 모두 구하여 permutation이 된 것 같다.
• itertools.combinations를 통해 쉽게 구할 수 있었다.

2. 모든 order의 가능한 조합들을 구한 뒤 course 배열 안에 있는 길이를 조회하여 해당 길이 중 가장 많이 찾은 조합을 정답에 추가해야 한다.

• 나는 모든 order의 가능한 조합들을 구한 뒤 반복문을 통해 각 course 길이와 같은 조합들을 찾고 dict에 저장하여 그 중 가장 자주 나온 order를 정답에 추가했다. 이는 (course 배열의 길이) x ( 모든 order의 조합들 ) 만큼의 반복문이 필요하고 복잡했다.
• 모든 order의 가능한 조합들을 구하는 것이 아닌 각 course_size마다 가능한 조합들만 비교한다. 이렇게 되면 각 반복문에서 course_size를 만족하는 조합들만 존재하므로 Counter().most_common() 을 통해 가장 많이 나온 조합을 쉽게 찾을 수 있다.

코드

• 개선한 코드

from collections import Counter
from itertools import combinations
def solution(orders, course):
    answer = []
    for course_size in course: # [2,3,4]
        order_combinations = [] # 가능한 모든 조합
        for order in orders:
            order_combinations += combinations(sorted(order),course_size)
        # comb -> (comb,count)
        order_combinations = Counter(order_combinations).most_common()
        # 가장 많이 나온 조합 찾기
        for tup in order_combinations:
            if( tup[1] == order_combinations[0][1] and tup[1] > 1 ):
                answer.append( "".join(tup[0]) )
    return sorted(answer)

• 이전 코드

from collections import defaultdict
from itertools import combinations
def find(menu_list,current):
    global d
    for i,menu in enumerate(menu_list):
        comb = current + menu_list[i]
        d[comb] += 1
        find(menu_list[:i]+menu_list[i+1:],comb)
def solution(orders, course):
    answer = []
    global d
    d = defaultdict(int)
    for order in orders:
        for i in course:
            c = list(combinations(order,i))
            for t in c:
                # 튜플 합치기
                s = ""
                for element in t:
                    s += element
                d["".join(sorted(s))] += 1
    for c in course:
        tmp = defaultdict(set)
        for key in d:
            # 코스의 길이
            if( len(key) == c ):
                tmp[d[key]].add("".join(sorted(key)))
        max_val = 0
        for i in tmp:
            max_val = max(max_val,i)
        if( max_val > 1 ):
            for i in tmp[max_val]:
                answer.append(i)
    return sorted(answer)