[프로그래머스/Python] Level 2_메뉴 리뉴얼(2021 KAKAO BLIND RECRUITMENT)

📌문제 유형

2021 KAKAO BLIND RECRUITMENT(구현)

 

📌문제

프로그래머스

 

📌나의 문제풀이

- 점수 : 85.0

from itertools import combinations
from collections import Counter

def solution(orders, course):
    menu = []
    ans = []
    
    #단품메뉴 추리기
    for menus in orders:
        for m in menus:
            if m not in menu:
                menu.append(m)
    
    # 메뉴 개수 별         
    for num in course:
        answer = []
        list_combi = list(combinations(menu,num))
        # combi 조합 
        for li_com in list_combi:
            cnt, max_ = 0,0
            # 손님이 주문한 조합(최대 20)
            for order in orders:
                tmp = set(order) - set(li_com)
                if tmp | set(li_com) == set(order):
                    cnt += 1
                    
            # 가장 많이 나오는 개수 출력 - 조금 더 효율적인 방법이 있을 거 같은데      
            if cnt >= 2:
                answer.append([li_com, cnt])
                
        answer.sort(key = lambda x:x[1], reverse = True)

        for menu_, max_ in answer:
            if max_ == answer[0][1]:
                ans.append(''.join(sorted(list(menu_))))
            else:
                break
    ans.sort()
    
    return ans

- 점수 : 100

• order과 list_combi 순서를 바꿈 -> 만들 수 있는 경우의 수가 줄어 시간초과 안 남! 

from itertools import combinations

def solution(orders, course):
    ans = []
        
    for num in course:
        answer = {}
        for order in orders:
            list_combi = list(combinations(sorted(order),num))
            for li_com in list_combi:
                cnt, max_ = 0,0
                tmp = set(order) - set(li_com)
                if tmp | set(li_com) == set(order):
                    if ''.join(li_com) in answer.keys():
                        answer[''.join(li_com)] += 1
                    else:
                        answer[''.join(li_com)] = 1
                
        answer = sorted(answer.items(), key = lambda x:x[1], reverse = True)
        
        for menu_, max_ in answer:
            if max_ == answer[0][1] and max_ > 1:
                ans.append(''.join(sorted(list(menu_))))
            else:
                break
    ans.sort()
    
    return ans

 

📌다른 사람의 문제풀이

- sort 대신 counter 이용

- 독립된 메뉴를 미리 찾지 않고, order 안에서 combination을 만들어서 검사 

from itertools import combinations
from collections import Counter

def solution(orders, course):
    ans = []
        
    for num in course:
        order_combi = []
        for order in orders:
            order_combi += combinations(sorted(order),num)
        most_ordered = Counter(order_combi).most_common()   # most_common : 개수 순으로 정렬하는 역할
        ans += [k for k,v in most_ordered if v>1 and v == most_ordered[0][1]]

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

 

📌리뷰

- combination 사용할 때, 아무리 단어길이가 적더라도 더 적게 활용할 수 있는 방법 고려해보기

- order 먼저 -> combination(sort)로 검사 -> dict에 넣어서 개수 세기 -> 많은 순서대로 정렬하기 

- 만약, combination에서 순서만 바뀐 단어가 count되고 있다면 sort 사용해서 순서 바뀐 단어 없애기