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

이번에 풀어볼 문제는 메뉴 리뉴얼이라는 문제이다.

문제

문제를 꼼꼼히 읽자..

처음에는 전체 조합 중에서 가장 많이 주문한 조합을 뽑는 걸로 착각했는데 잘 읽어보면 코스 요리의 개수마다 가장 많이 주문한 조합 중에서 그 조합을 시킨 사람이 2명 이상인 것들을 모아서 문자열의 오름차순 리스트를 만들어서 반환해야하는 문제이다

풀이 과정

• 이 문제를 보자마자 무슨 알고리즘을 써야겠다! 라는 아이디어가 안떠올라서 이것도 생각나는 대로 짜보았다

1. 코스 요리 개수 마다 각 주문에 대한 조합을 구함
2. 조합 중에서 가장 많이 나왔던 조합을 각 코스 요리 개수 마다 저장함
3. 2에서 저장한 결과를 문자열 기준으로 오름차순으로 정렬

from itertools import combinations

def solution(orders, course):
    answer = []
    
    
    for course_item in course:
        comb_count = {}
        order_combinations = []
        
        max_order = []
        for order in orders:
            order_comb = combinations(list(order), course_item)
            
            for order in order_comb:
                order_comb_string = "".join(sorted(order))
                
                if comb_count.get(order_comb_string):
                    comb_count[order_comb_string] += 1
                    
                else:
                    comb_count[order_comb_string] = 1
            
        max_order = [k for k,v in comb_count.items() if ((v == max(comb_count.values())) and v >= 2) ]
        
        answer.extend(max_order)
        
    
    answer = sorted(answer)
    
    
    return answer

결과는 모두 통과!

다른 사람 풀이

from itertools import combinations
from collections import Counter
def solution(orders, course):
    answer = []
    for k in course:
        candidates = []
        for menu_li in orders:
            for li in combinations(menu_li, k):
                res = ''.join(sorted(li))
                candidates.append(res)
        sorted_candidates = Counter(candidates).most_common()
        answer += [menu for menu, cnt in sorted_candidates if cnt > 1 and cnt == sorted_candidates[0][1]]
    return sorted(answer)

• 나는 주문조합의 개수를 셀 때 dictionary와 sorted를 사용했는데, Counter라는 모듈을 사용하면 더 쉽게 할 수 있다는 걸 배웠다.
  - Counter함수는 해당 함수는 리스트에 원소가 몇 번 나왔는지 세줌
  - Counter의 most_common() 메서드는 데이터의 개수가 많은 순으로 정렬된 배열을 리턴함

개념

• 이 문제를 풀기 위해서 공부한 내용을 정리한다

조합, 순열

from itertools import permutations, combinations, permutations, product, combinations_with_replacement

permutations('abcd', repeat=2) //repeat=2는 두개를 뽑는다는 뜻

이런식으로 import해서 사용하면 된다

product는 데카르트 곱이라고도 하는데, 두개 이상의 리스트의 조합을 구할 때 유용하게 사용한다고 한다.

from itertools import product

_list = ["012", "abc", "!@#"]
pd = list(product(*_list))
# [('0', 'a', '!'), ('0', 'a', '@'), ('0', 'b', '!'), ('0', 'b', '@'), ('1', 'a', '!'), ('1', 'a', '@'), ('1', 'b', '!'), ('1', 'b', '@')]

A = [1,2,3]
list(itertools.product(A, repeat=2)) //list()를 안해주면 주소값으로 나옴
>>>> [(1, 1), (1, 2), (1, 3), (2, 1), (2, 2), (2, 3), (3, 1), (3, 2), (3, 3)]

permutations는 nPr으로, 서로다른 n개의 요소중에 r개를 뽑아 순서가 있게 배열한 것이다.즉 순서를 고려해서 중복없이 뽑을 경우의 수라고 보면 된다.

combinations는 nCr으로 서로다른 n개의 요소중에 순서를 고려하지 않고 중복 없이 뽑는 경우의 수이다.

combinations_with_replacement는 nHr으로, 중복 가능한 n개중에서 r개를 순서없이 선택하는 경우의 수를 의미한다.