[프로그래머스 Lv2.] 메뉴 리뉴얼(python)

1. 문제

문제 설명

제한사항

입출력

입출력 예시

2. 풀이 과정

내가 생각한 진행 과정

• 우선, 가능한 모든 코스요리 메뉴를 combination으로 만들면서, 해당 코스요리별 갯수를 표시한 dictionay를 만듦(new_menu = {'AC':2,,,})
  • 이때, 메뉴를 정렬한 후에 dictionary를 만들어야함 -> 여기서 정렬안해주면, XW, WX를 다른것으로 인식함
• new_menu를 갯수가 많은것부터 정렬(sort_menu)
• sort_menu의 첫번째 값의 갯수가 최대 값임. 이때, sort_menu = []일 수 있으므로, sort_menu가 뭐라도 있을 때 mymax구하기
• mymax를 구했다면, sort_menu 돌면서 mymax와 동일한 갯수를 가지고있다면, answer에 넣기

코드

from itertools import combinations

def solution(orders, course):
    answer = []
    for c in course:
        candidates = []
        new_menu = {}
        for menu in orders:
            menu_li = list(''.join(menu))
            for li in combinations(menu_li, c):
                res = ''.join(sorted(li))  # 여기서 정렬안해주면, XW, WX를 다른것으로 인식함
                if res not in new_menu:
                    new_menu[res] = 1
                else:
                    new_menu[res] += 1
        sort_menu = sorted(new_menu.items(), reverse=True, key=lambda x: x[1])

        if len(sort_menu):  # sort_menu = []일 수 있음
            mymax = sort_menu[0][1]

            if mymax > 1:
                for i in sort_menu:
                    if i[1] == mymax:
                        answer.append(i[0])

    answer = sorted(answer)

    return answer

3. 다른 풀이 방법

• 가능한 모든 조합을 다 뽑아낸 다음에 각 조합의 개수마다 가장 많이 나온 메뉴 선택 -> 시간복잡도 증가 + 특정 개수에서 가장 많이 나온 메뉴를 찾기가 힘듦
• Counter 사용 - 딕셔너리를 사용해서 개수를 파악
  • counter 함수는 배열에 원소가 몇 번 나왔는지 쉽게 알려줌
  • 딕셔너리 사용이 필요 없음
  • Counter의 most_common() 메서드로 데이터의 개수가 많은 순으로 정렬된 배열을 리턴받을 수 있음

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)