[Python] 2021 KAKAO BLIND RECRUITMENT 메뉴 리뉴얼

https://school.programmers.co.kr/learn/courses/30/lessons/72411?language=python3 

프로그래머스

 

- 문제 파악

1. 메뉴는 최소 2가지 이상의 단품메뉴로 구성한다.
2. 최소 2명 이상의 손님으로부터 주문된 단품메뉴 조합에 대해서만 코스요리 메뉴 후보에 포함한다.
3. 코스요리 메뉴의 구성을 문자열 형식으로 배열에 담아 사전순으로 오름차순 정렬하여 return한다.
4. 배열의 각 요소들 또한 알파벳 오름차순으로 정렬된다.

 

- 문제 해결 흐름

1. course 배열의 원소를 순회하며 각 손님이 주문한 메뉴의 조합을 구한다.
course = [2, 3, 4], orders = ["ABCD", "ABGH"] 인 경우를 예를 들면
course 배열의 2 원소를 순회할 때,
orders 배열을 순회하며 2개의 메뉴 조합은 각각  [AB, AC, AD, BC, CD], [AB, AG, AH, BG, BH, GH] 이렇게 나온다.dictionary 자료구조를 사용하여 각 조합을 체크해준다.
dic = {AB:2, AC:1, AD:1, BC:1, CD:1, AG:1, AH:1, BG:1, BH:1, GH:1} 

 

def solution(orders, course):
    global answer_dict
    answer = []
    
    for num in course:	# course의 메뉴 개수 순회
        answer_dict = {}	# 모든 조합을 체크해줄 dictionary 자료구조에 
        for element in orders:		# 코스요리 배열 순회 
            element = "".join(sorted(element))	# 각 원소에 저장된 문자열 또한 알파벳 오름차순으로 정렬해야하는 조건이 있다.
            search(crnt_list=[], n=num, elem=element, dictionary=answer_dict, start=0)	# 조합 탐색

# 조합해주는 함수
def search(crnt_list, n, elem, dictionary, start):
    if(len(crnt_list) == n):
        crnt_list.sort()
        menu = ''.join(crnt_list)
        if not dictionary.get(menu):
            dictionary[menu] = 1
        else:
            dictionary[menu] += 1
        return
    
    for i in range(start, len(elem)):
        crnt_list.append(elem[i])
        search(crnt_list, n, elem, dictionary, i+1)
        crnt_list.pop()

 

answer_dict에 담긴 체크된 조합

2. 최소 2명 이상의 손님으로부터 주문된 단품메뉴 조합에 대해서만 코스요리 메뉴 후보에 포함할 수 있는 조건이 있다.
위에 모든 조합을 체크해준 dic에서 2개 이상인 최댓값을 구하여 정답으로 return할 answer 배열에 append한다.

for i in [k for k,v in answer_dict.items() if max(answer_dict.values()) == v and v >= 2]:
            answer.append(i)

3. 오름차순으로 정렬하여 return한다

 

 

Python

answer_dict = {}	# 조합 체크해줄 dict 전역변수로 초기화

def search(crnt_list, n, elem, dictionary, start):	# 조합을 만드는 함수
    if(len(crnt_list) == n):
        crnt_list.sort()
        menu = ''.join(crnt_list)
        if not dictionary.get(menu):
            dictionary[menu] = 1
        else:
            dictionary[menu] += 1
        return
    
    for i in range(start, len(elem)):
        crnt_list.append(elem[i])
        search(crnt_list, n, elem, dictionary, i+1)
        crnt_list.pop()

def solution(orders, course):
    global answer_dict
    answer = []
    
    for num in course:
        answer_dict = {}	
        for element in orders:
            element = "".join(sorted(element))	# 조건 중에 요소들 또한 알파벳 오름차순 정렬
            search(crnt_list=[], n=num, elem=element, dictionary=answer_dict, start=0)	# 조합 함수 실행
            # answer_dict dictionary에 모든 조합이 체크되어 담긴다.
            # value가 2이상인 최댓값을 answer 배열에 append한다.
        for i in [k for k,v in answer_dict.items() if max(answer_dict.values()) == v and v >= 2]:
            answer.append(i)
	# answer 배열 알파벳 오름차순 정렬
    answer.sort()
    return answer