프로그래머스 파이썬 : 메뉴리뉴얼

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

프로그래머스

문제 풀이

1. 주문 하나씩 가져와서 가능한 course 수 만큼 모든 조합을 구한다. (itertools, combinations 이용)
2. 조합과 해당 조합의 개수를 딕셔너리로 저장한다.
3. 가능한 코스의 요리개수를 구한다.
4. 가능한 요리개수마다, 주문수가 최대인 주문만 결과 리스트에 추가하고 return한다.

 

공부한 것

1. 순열 조합 itertools

from itertools import combinations, permutations

p = itertools.permutations(list_n, r)  # 순열
p = list(p)
c = itertools.combinations(list_n, r)  # 조합
c = list(c)

 

2. lambda 정렬

all.sort(key=lambda x:-x[1])

lambda 정렬에서 내림차순으로 하려면 -를 붙인다!

 

 

코드

from itertools import combinations

def solution(orders,course):
    all=dict()
    for order in orders:
        n=len(order)
        if n<course[0]:
            continue
        for c in course:
            order=list(order)
            order.sort()
            temp=list(combinations(order,c))
            for t in temp:
                t=''.join(t)
                all[t]=all.get(t,0)+1

    all = [(key,value) for key,value in all.items() if value>=2]
    all.sort(key=lambda x:-x[1])
    answer=[]
    for cnt in course:
        max_order=0
        for d in all:
            d_order=d[cnt]
            d_len = len(d[0])
            if d_len==cnt:
                if d_order>=max_order:
                    max_order=d_order
                    if d[0] not in answer:
                        answer.append(d[0])
    answer.sort()
    return answer

course 하나마다 전체 반복문을 돌았으면 최대값 찾기도 편리했을 것 같은데,

한번에 다 하다보니 마지막 반복문이 조금 복잡해진것같다.

 

주문 조합을 모두 담아주는 all 딕셔너리의 변화를 보면,

{'AB': 2, 'AC': 2, 'AD': 3, 'AE': 2, 'BC': 1, 'BD': 1, 'BE': 1, 'CD': 3, 'CE': 1, 'DE': 2, 'ABC': 1, 'ABD': 1, 'ABE': 1, 'ACD': 2, 'ACE': 1, 'ADE': 2, 'BCD': 1, 'BCE': 1, 'BDE': 1, 'CDE': 1, 'ABCDE': 1, 'XY': 2, 'XZ': 2, 'YZ': 2, 'XYZ': 2}

처음에 모든 주문의 조합과 개수를 담는다.

 

[('AD', 3), ('CD', 3), ('AB', 2), ('AC', 2), ('AE', 2), ('DE', 2), ('ACD', 2), ('ADE', 2), ('XY', 2), ('XZ', 2), ('YZ', 2), ('XYZ', 2)]

1개인 주문은 없애고, 내림차순 정렬한다.

 

그리고나서 course의 요소마다 반복문을 돌리며 비교하는데,

개수에 대해 내림차순 정렬을 했기 때문에 max_order과 같을 때 answer에 답을 넣어줘도 문제가 없었다.

만약에 내림차순  정렬을 하지 않았다면, 이미 answer에 담겨져있는 요소를 처리하기가 어렵다고 생각했다.

 

 

 

 

 

def solution(orders, course):
    answer = []
    for n in course:
        n_dict = {}
        for order in orders:
            if len(order) >= n:
                o_lst = list(order)
                comb = list(itertools.combinations(o_lst, n))
                for c in comb:
                    c = sorted(list(c))
                    s = ''.join(c)
                    n_dict[s] = n_dict.get(s, 0) + 1
        if len(n_dict):
            max_val = max(list(n_dict.values()))
            if max_val >= 2:
                for k, v in n_dict.items():
                    if v == max_val:
                        answer.append(k)
    answer.sort()
    return answer

다른사람의 코드인데, 방식은 같지만 n_dict를 보면 반복문마다 하나씩 만들고, 반복문마다 answer이 추가되는 형식이다.

 

n_dict를 보면 아래와 같다.

course=[2,3,5]인 케이스일 때를 예시로 생각하면,

 

course 첫번째 반복문(2일때)

{'AB': 2, 'AC': 2, 'AD': 3, 'AE': 2, 'BC': 1, 'BD': 1, 'BE': 1, 'CD': 3, 'CE': 1, 'DE': 2, 'XY': 2, 'XZ': 2, 'YZ': 2}

-> result : ['AD', 'CD']

 

course 두번째 반복문(3일때)
{'ABC': 1, 'ABD': 1, 'ABE': 1, 'ACD': 2, 'ACE': 1, 'ADE': 2, 'BCD': 1, 'BCE': 1, 'BDE': 1, 'CDE': 1, 'XYZ': 2}

-> result : ['AD', 'CD', 'ACD', 'ADE', 'XYZ']

 

course 세번째 반복문(5일때)
{'ABCDE': 1}

-> result : ['AD', 'CD', 'ACD', 'ADE', 'XYZ']

 

이렇게 되는 것이다.

딕셔너리에 하나의 course 개수만 담기기때문에 최대값을 구하기도 편리한 것 같다.

 

 

 

 

테스트케이스 결과

테스트 1 〉	통과 (0.14ms, 10.4MB)
테스트 2 〉	통과 (0.08ms, 10.1MB)
테스트 3 〉	통과 (0.10ms, 10.3MB)
테스트 4 〉	통과 (0.10ms, 10.3MB)
테스트 5 〉	통과 (0.10ms, 10.3MB)
테스트 6 〉	통과 (0.47ms, 10.3MB)
테스트 7 〉	통과 (0.28ms, 10.2MB)
테스트 8 〉	통과 (2.32ms, 10.4MB)
테스트 9 〉	통과 (1.79ms, 10.3MB)
테스트 10 〉	통과 (1.90ms, 10.6MB)
테스트 11 〉	통과 (0.97ms, 10.4MB)
테스트 12 〉	통과 (1.08ms, 10.5MB)
테스트 13 〉	통과 (1.75ms, 10.6MB)
테스트 14 〉	통과 (0.91ms, 10.6MB)
테스트 15 〉	통과 (2.88ms, 10.5MB)
테스트 16 〉	통과 (0.61ms, 10.4MB)
테스트 17 〉	통과 (0.38ms, 10.3MB)
테스트 18 〉	통과 (0.17ms, 10.1MB)
테스트 19 〉	통과 (0.03ms, 10.4MB)
테스트 20 〉	통과 (0.53ms, 10.3MB)