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

메뉴 리뉴얼

문제 설명

각 손님들이 주문한 단품메뉴들이 문자열 형식으로 담긴 배열 orders, "스카피"가 추가하고 싶어하는 코스요리를 구성하는 단품메뉴들의 갯수가 담긴 배열 course가 매개변수로 주어질 때, "스카피"가 새로 추가하게 될 코스요리의 메뉴 구성을 문자열 형태로 배열에 담아 return 하도록 solution 함수를 완성해 주세요.

제한사항

• orders 배열의 크기는 2 이상 20 이하입니다.
• orders 배열의 각 원소는 크기가 2 이상 10 이하인 문자열입니다.
  • 각 문자열은 알파벳 대문자로만 이루어져 있습니다.
  • 각 문자열에는 같은 알파벳이 중복해서 들어있지 않습니다.
• course 배열의 크기는 1 이상 10 이하입니다.
  • course 배열의 각 원소는 2 이상 10 이하인 자연수가 오름차순으로 정렬되어 있습니다.
  • course 배열에는 같은 값이 중복해서 들어있지 않습니다.
• 정답은 각 코스요리 메뉴의 구성을 문자열 형식으로 배열에 담아 사전 순으로
  • 배열의 각 원소에 저장된 문자열 또한 알파벳 오름차순으로 정렬되어야 합니다.
  • 만약 가장 많이 함께 주문된 메뉴 구성이 여러 개라면, 모두 배열에 담아 return 하면 됩니다.
  • orders와 course 매개변수는 return 하는 배열의 길이가 1 이상이 되도록 주어집니다.
• 오름차순으로 정렬해서 return 해주세요.

풀이

입력값이 작길래 무식하게 풀었다

from collections import Counter
from itertools import combinations
import heapq
​
def solution(orders, course):
    answer = []
    chars = {}
    counter = Counter()
    for order in orders: # 각 알파벳 등장 횟수 세기
        counter += Counter(order)
    
    len_cnt = Counter([len(x) for x in orders]) #각 order 길이 저장 
    
    counter = [k for k in counter.keys() if counter[k] >= 2] # 2번 이상 주문된 메뉴만 추림
    
    for c in counter:# 각 알파벳별 포함하는 order 저장
        for order in orders:
            if c in order:
                chars.setdefault(c, [])
                chars[c].append(order)
                
    for c in course:
        heap = []
        # 만약 최대 길이인데 한번만 주문됐다면 패스
        if c == max(len_cnt.keys()) and len_cnt[c] == 1:
            continue
        # 문자열로 조합 만들기
        for c in combinations(counter,c):
            case = ''.join(sorted(c)) # 오름차순으로 정렬 후 문자열로 변환
            ordered = 0
            for order in chars[case[0]]: # 첫번째 문자가 등장한 order들에서
                for c in case[1:]: # 나머지 문자가 포함되어 있는지 확인
                    if c not in order:
                        break
                else: # 모두 포함되어 있다면 주문횟수 카운트
                    ordered += 1
            if ordered >= 2: # 주문 횟수 2 이상이면 힙에 넣기
                heapq.heappush(heap, (-ordered, case))
            
        if heap:
            cnt, case = heapq.heappop(heap) 
            answer.append(case)
            while heap and heap[0][0] == cnt: # 최대값 다 꺼내기
                _, case = heapq.heappop(heap)
                answer.append(case)
                
    return sorted(answer)

다른 사람 풀이

Counter 클래스의 most_common 메소드를 사용하면 힙을 사용하지 않아도 된다.

most_common메소드는 데이터의 개수가 많은 순으로 정렬된 배열을 리턴해준다.

숫자 k를 넘기면 그 숫자만큼만 리턴하기 때문에 가장 개수가 많은 K개의 데이터를 얻을 수도 있다.

조합을 만든 다음에 각 문자열에서 확인하는 게 아니라 각 문자열에서 가능한 조합을 만들어서 조합 리스트에 붙이고 그 중 데이터 개수가 많은 것들만 결과에 포함하면 된다.

from collections import Counter
from itertools import combinations
​
def solution(orders, course):
    result = []
​
    for course_size in course:
        order_combinations = []
        for order in orders:
            order_combinations += combinations(sorted(order), course_size)
        
        most_ordered = Counter(order_combinations).most_common()
        # 1번 이상 주문된 최댓값만 배열로 만들기
        result += [ k for k, v in most_ordered if v > 1 and v == most_ordered[0][1] ]
​
    return [ ''.join(v) for v in sorted(result) ]
​