사용자 도구

사이트 도구


ps:problems:programmers:72411

메뉴 리뉴얼

ps
링크https://programmers.co.kr/learn/courses/30/lessons/72411
출처프로그래머스
문제 번호72411
문제명메뉴 리뉴얼
레벨Level 2
분류

구현

시간복잡도O(n*2^m)
인풋사이즈n<=10, m<=20
사용한 언어Python
해결날짜2021/01/25
출처2021 KAKAO BLIND RECRUITMENT

풀이

  • 효율적인 방법은 딱히 없다. n이 작으니 주문이 한번 올 때마다, 모든 부분집합을 다 구해서 카운터를 각각 올려주는 무식한 방법으로 해결 가능
    • 모든 요리 조합에 대해서 주문 횟수를 세는 것은 O(n*2^m). (n=주문의 갯수, m=한번 주문에 포함가능한 요리 갯수)
    • 코스의 크기별로 가장 많이 주문된 조합을 찾는 것은, 모든 크기에 대해서 쿼리가 들어온 경우에, 최대로 전체 조합의 갯수만큼 걸린다. 즉, 이것도 역시 O(n*2^m).
  • itertools.combinations와 collections.Counter가 유용하게 쓰인다
  • 하지만, 그래도 이것저것 구현에 신경써야 하는 사소한 것들이 많다.

코드

"""Solution code for "Programmers 72411. 메뉴 리뉴얼".

- Problem link: https://programmers.co.kr/learn/courses/30/lessons/72411
- Solution link: http://www.teferi.net/ps/problems/programmers/72411
"""

import collections
import itertools

MAX_MENU_COUNT = 10


def solution(orders, course):
    counter_by_size = [collections.Counter() for _ in range(MAX_MENU_COUNT + 1)]
    for order in orders:
        for i in range(2, len(order) + 1):
            counter_by_size[i].update(itertools.combinations(sorted(order), i))

    answer = []
    for menu_count in course:
        menus_and_count = counter_by_size[menu_count].most_common()
        if menus_and_count and (max_count := menus_and_count[0][1]) >= 2:
            for m, c in menus_and_count:
                if c != max_count:
                    break
                answer.append(''.join(m))

    return sorted(answer)

토론

댓글을 입력하세요:
N C S R᠎ Q
 
ps/problems/programmers/72411.txt · 마지막으로 수정됨: 2021/01/30 14:23 저자 teferi