[알고리즘] 프로그래머스 - 메뉴 리뉴얼

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

내 풀이

from itertools import combinations
from collections import defaultdict

def solution(orders, course):
    answer = []
    count_dict = defaultdict(int)
    for order in orders:
        order = list(order)
        for count in range(2, len(order)+1):
            combs = list(combinations(order, count))
            for comb in combs:
                count_dict[tuple(sorted(comb))] += 1

    ans_dict = defaultdict(tuple) # key: 길이 value: 코스, 선택받은 횟수?

    for course_count in course:
        for k, v in count_dict.items():
            if len(k) == course_count and v >= 2:
                if ans_dict[course_count]:
                    existed_value = ans_dict[course_count]
                    existed_count = existed_value[-1]
                    if v > existed_count:
                        ans_dict[course_count] = (k, v)
                    elif v == existed_count:
                        existed_value_list = list(existed_value)
                        existed_value_list = existed_value_list[:-1]
                        existed_value_list.append(k)
                        existed_value_list.append(v)
                        ans_dict[course_count] = tuple(existed_value_list)
                else:
                    ans_dict[course_count] = (k, v)

    for k, v in ans_dict.items():
        comb = list(v)
        comb = comb[:-1]
        for item in comb:
            answer.append(''.join(item))

    return sorted(answer)

print(solution(["ABCFG", "AC", "CDE", "ACDE", "BCFG", "ACDEH"], [2,3,4]) ==["AC", "ACDE", "BCFG", "CDE"])
print(solution(["ABCDE", "AB", "CD", "ADE", "XYZ", "XYZ", "ACD"], [2,3,5]) ==["ACD", "AD", "ADE", "CD", "XYZ"])
print(solution(["XYZ", "XWY", "WXA"], [2,3,4]) == ["WX", "XY"])

다른 사람 풀이

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()
        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)]