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

[문제링크] (https://programmers.co.kr/learn/courses/30/lessons/72411)

1. 문제 설명

• 입력 orders : 각 손님들이 주문한 단품메뉴들이 문자열 형식으로 담긴 배열 course : "스카피"가 추가하고 싶어하는 코스요리를 구성하는 단품메뉴들의 갯수가 담긴 배열
• 출력 "스카피"가 새로 추가하게 될 코스요리의 메뉴 구성을 문자열 형태로 배열에 담아 return 사전순으로 오름차순 정렬
• 규칙 (1) 가장 많이 주문한 단품 메뉴들을 코스요리 메뉴로 구성 ex1 ) AC가 네번, CD는 세번 일 때 → AC를 두개까지 요리2개코스로 채택 ex2) BCFG가 두번, ACDE가 두 번 주문됨 → 둘 다 요리4개코스로 채택

(2) 코스요리는 최소 2가지 이상의 단품 메뉴로 구성 (3) 최소 두 명 이상의 손님이 주문한 단품요리만 코스요리의 후보가 됨

2. 입출력 예시

orders	course	result
["ABCFG", "AC", "CDE", "ACDE", "BCFG", "ACDEH"]	[2,3,4]	["AC", "ACDE", "BCFG", "CDE"]
["ABCDE", "AB", "CD", "ADE", "XYZ", "XYZ", "ACD"]	[2,3,5]	["ACD", "AD", "ADE", "CD", "XYZ"]
["XYZ", "XWY", "WXA"]	[2,3,4]	["WX", "XY"]

3. 코드

from itertools import combinations

def solution(orders, course):
    answer = []
    foodMap = [{} for _ in range(11)] #메뉴 개수에 따라 딕셔너리를 사용(2~10까지 11개사용)
    maxCnt = [0 for _ in range(11)] #메뉴 개수별 최대등장횟수 저장 

    for str in orders:
    	#코스를 구성하는 메뉴의 갯수는 두개 이상, 문자열 길이만큼 메뉴개수를 진행 AC면 두개, CDE면 두개혹은세개
        for num in range(2,len(str)+1): 
        	#input으로 주어지는 문자열을 sort해서 전달, 정렬된 상태로 개수(num)만큼 조합을 만들어서 튜플형태로 리스트로 반환
            for i in combinations(sorted(str),num): 
                key = ''.join(i) #string으로 변환하여 사용
                if key in foodMap[num]: #메뉴구성이 이미있으면
                    foodMap[num][key] +=1
                    maxCnt[num] = max(maxCnt[num],foodMap[num][key])
                else:
                    foodMap[num][key] = 1
    
    for num in course:
        for key, value in foodMap[num].items():
            if value >=2 and value == maxCnt[num]: #두개 이상인것, 최대값과 같은 모든 것
                answer.append(key)

    return sorted(answer)

세 번째 입출력 예시 기준 변수 설명

• foodMap : 두개조합코스요리, 세개조합코스요리 등등 각 메뉴갯수별 후보들을 담고 그 후보들의 orders에서의 등장횟수를 count
  • [{}, {}, {'XY': 2, 'XZ': 1, 'YZ': 1, 'WX': 2, 'WY': 1, 'AW': 1, 'AX': 1}, {'XYZ': 1, 'WXY': 1, 'AWX': 1}, {}, {}, {}, {}, {}, {}, {}]
• maxCnt : 메뉴갯수별 최대 등장횟수를 count
  • [0, 0, 2, 1, 0, 0, 0, 0, 0, 0, 0]
• answer
  • ['XY', 'WX']

4. 어렵거나 헷갈렸던 점

1. 문제이해하기

가장 많이 주문한 단품 메뉴들을 코스요리 메뉴로 구성

예를 들어, AC가 네번, CD는 세번 일 때, AC를 두개까지 코스요리로 채택해야 한다.

글을 읽다가 난독증이와서 이 부분을 캐치하지 못했다..

1. 조합을 어떻게 조사할지

from itertools import combinations 을 사용

조합은 선택하고 선택안하고로 이루어진다.

5. 참고 자료

https://www.youtube.com/watch?v=PnXovk2JtU4