PROGRAMMERS 72411: 메뉴 리뉴얼

Link : https://programmers.co.kr/learn/courses/30/lessons/72411

---

Python

def DFS(arr, deapth, items, length):
    """
        특정 길이의 모든 조합을 문자열로 반환해주는 함수
    :param arr: 현재 리스트
    :param deapth: 현재 길이
    :param items: 조합 할 목록들
    :param length: 조합 길이
    :return: 모든 조합의 문자열
    """
    result = []
    if deapth == length:  # 조합 길이와 현재 깊이가 같다면
        return ''.join(arr)  # 반환
 
    # 조합 할 목록들을 반복함
    for idx, item in enumerate(items):
        arr.append(item)  # 조합 목록 추가
        # ABCD라면 A가 추가 되었으므로 다음 조합은 BCD이므로 [idx + 1:] 로 진행함.
        result.append(DFS(arr, deapth + 1, items[idx + 1:], length))
        # AB 상태에서 빠져 나왔으면 AC가 되어야 함으로 B를 pop해줌
        arr.pop()
 
    return ' '.join(result)
 
 
def getCombination(items, length):
    """
        특정 길이의 모든 조합을 리스트화 시켜 반환해주는 함수
    :param items: 조합 할 목록들
    :param length: 조합 길이
    :return: 모든 조합의 리스트
    """
    return [i for i in DFS([], 0, items, length).split(' ') if i != ""]
 
 
def solution(orders, course):
    answer = set()
    for c in course:
        combi = []
        for order in orders:
            # c길이 만큼의 모든 조합을 가져옴 단, 문제의 의도에 따라 order를 오름차순 정렬 하였음.
            combi += getCombination(sorted(order), c)
 
        # 만약 조합 할 목록이 없으면 다음으로
        if len(combi) == 0:
            continue
 
        # 조합 중 가장 많이 뽑힌 조합의 길이를 가져옴
        max_order = combi.count(max(combi, key=lambda x: combi.count(x)))
 
        # 만약 길이가 1이라면 여러번 뽑힌 조합이 아니므로 다음으로
        if max_order == 1:
            continue
 
        for i in combi:
            # 모든 조합 중 최대 조합과 같으면 정답에 추가 함
            if combi.count(i) == max_order:
                answer.add(i)  # set이기 때문에 중복이 없음
    return sorted(list(answer))

FeedBack

1. 찾아보니 itertools에 combinations 라는 라이브러리가 있었다...

---

 

 

 

cjw.git@gmail.com