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

문제

구현 문제이다.

처음에 모든 조합을 combination을 구현하여, 모든 조합을 구했다,,!!(itertools에 combination이 있다,,,)

dictionary를 사용하여, 각 조합의 갯수를 구했다.(이것도 collections의 Counter를 사용하면 되긴하다.)

이후에 dq를 사용하여, 동일한 길이의 조합 중에 가장 많은 갯수의 조합을 왼쪽에 놓았다.

dq의 앞에가 가장 큰 값이기 때문에 그 값과 비교하여, 같은 조합만 answer에 넣어주고 작은 값이 나오면 break해주었다.

answer의 값들을 sort해주어서 return 했다.

코드

from collections import deque
def solution(orders, course):
    answer = []
    combi = []
    for o in orders:
        for c in course:
            combi += combination("",sorted(o), c)
    # 각 조합의 갯수 저장
    dic = {}
    for co in combi:
        if co in dic:
            dic[co] += 1
        else:
            dic[co] = 1
    dqList = [deque([]) for i in range(course[-1] + 1)]
    # 동일한 길이의 가진 문자열 중 가장 많은 조합의 갯수를 queue 왼쪽에 저장.
    for k,v in dic.items():
        
        if len(dqList[len(k)]) == 0:
            dqList[len(k)].append([v,k])
        else:
            if dqList[len(k)][0][0] <= v:
                dqList[len(k)].appendleft([v,k])
    
    # 동일한 길이의 가진 문자열 중 가장 많은 조합의 갯수들을 찾아 answer에 저장
    for dq in dqList:
        if len(dq) == 0:
            continue
        maxNum = dq[0][0]
        # 가장 큰 값이 2보다 작으면 코스요리에 넣지 않는다.
        if maxNum < 2:
            continue
        answer.append(dq[0][1])
        dq.popleft()
        while len(dq) > 0:
            if maxNum == dq[0][0]:
                answer.append(dq[0][1])
                dq.popleft()
            else:
                break
    # 알파벳 순으로 sort
    answer.sort()
    return answer

def combination(tmp,o, c):
    ls = []
    if len(tmp) == c:
        return [tmp]
    for i in range(len(o)):
        tmp += o[i]
        ls += combination(tmp, o[i+1:], c)
        tmp = tmp[:-1]

    return ls
"""
코스 요리
주문할 때 가장 많이 함께 주문한 단품메뉴들을 코스요리 메뉴로 구성
코스요리 메뉴 = 최소 2가지 이상의 단품메뉴 and 최소 2명 이상의 손님한테 제공
새로 추가하게 될 코스요리의 메뉴 구성을 문자열 return
course에 나온 갯수대로 배열을 만들고, 조합들을 만들기.
조합
"""