[Programmers] 메뉴 리뉴얼

https://school.programmers.co.kr/learn/courses/30/lessons/72411

프로그래머스

 

문제 설명

레스토랑을 운영하던 스카피는 코로나19로 인한 불경기를 극복하고자 메뉴를 새로 구성하려고 고민하고 있습니다.
기존에는 단품으로만 제공하던 메뉴를 조합해서 코스요리 형태로 재구성해서 새로운 메뉴를 제공하기로 결정했습니다. 어떤 단품메뉴들을 조합해서 코스요리 메뉴로 구성하면 좋을 지 고민하던 "스카피"는 이전에 각 손님들이 주문할 때 가장 많이 함께 주문한 단품메뉴들을 코스요리 메뉴로 구성하기로 했습니다.
단, 코스요리 메뉴는 최소 2가지 이상의 단품메뉴로 구성하려고 합니다. 또한, 최소 2명 이상의 손님으로부터 주문된 단품메뉴 조합에 대해서만 코스요리 메뉴 후보에 포함하기로 했습니다.

 

제한사항

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

처음 시도

def solution(orders, course):
    answer = []
    orders_sorted = [
    for order in orders:
        order = list(order)
        order.sort()
        orders_sorted.append(order)
        
    menu = []
    for i in course:
        cnt = 0
        for _ in range(20-i):
            for j in range(len(orders)):
                if len(orders[j]) < (i+cnt):
                    continue
                if orders[j][cnt:cnt+i] in menu:
                    answer.append(orders[j][cnt:cnt+i])
                menu.append(orders[j][cnt:cnt+i])
            cnt += 1
        

    answer_dict = {}
    for ans in answer:
        if answer_dict.get(ans) == None:
            answer_dict[ans] = 1
        else:
            answer_dict[ans] += 1
    
    course_max = [False]*sum(course)
    for key,val in answer_dict.items():
        if not course_max[len(key)]:
            course_max[len(key)] = [key, answer.count(key)]
        else:
            if course_max[len(key)][1] == answer.count(key):
                course_max[len(key)].append([key, answer.count(key)])
            elif course_max[len(key)][1] < answer.count(key):
                course_max[len(key)] = [key, answer.count(key)]
    print(course_max)
    
    return answer

생각보다 제한사항에 나와있는 값들의 범위가 작은 것 같아 하나하나 다 비교하려 했다 .. 

1. 모든 코스 갯수에 대해

2. 모든 주문을 오름차순 정렬한 후, 0인덱스부터 탐색하는데 (ex. 2코스라면 0~1, 2~3, 4~5, .. )

3. 만약 다른 주문들이 해당 범위만큼 탐색 시 같은 주문이 있으면 answer에 추가하게 된다.

4. 이후에 딕셔너리를 활용해 2번 이상 주문시킨 메뉴의 길이별로 최대 주문량이 있는 메뉴를 구한다 ....

 

다시봐도 너무 난해한 로직이다. 😂

 

그럼 정답을 봐보자.

Step1)

각 메뉴별로 가능한 모든 조합을 만든다.

Step2)

조합하려는 개수(K)를 선정했다면 orders에 있는 원소들로 가능한 조합을 만든다.

Step3)

가능한 조합을 만들면서 해당 조합이 몇개가 등장하는지 개수를 카운트한다.

Step4)

sorted, lambda를 이용해 딕셔너리를 정렬하고 가장 많이 나온 조합을 answer에 담는다.

Step5)

answer에 담긴 메뉴들을 사전순으로 정렬한다.

 

그렇다.. 이렇게 조건이 작고 경우의 수를 따져봐야 하는 경우에는

"조합"과 관련된 라이브러리를 떠올리자!

 

이건 Counter라는 라이브러리를 사용하면 간편하게 구현 가능하다.

 

from itertools import combinations
from collections import Counter # 항목의 갯수를 셀 때 사용하는 클래스 Counter

def solution(orders, course):
    answer = []
    for k in course: # 코스 종류 하나씩 탐색 (몇 개 코스인지)
        candidates = []
        for menu_li in orders: # 주문 하나씩 탐색
            for li in combinations(menu_li, k): # 주문한 메뉴들 k개(k개 코스) 조합 만들기
                res = ''.join(sorted(li)) # 조합 하나의 문자로 변환, 정렬해서 저장
                candidates.append(res)
        sorted_candidate = Counter(candidates).most_common() # 각 조합 몇개 있는지 세어서 내림차순 정렬
        answer += [menu for menu, cnt in sorted_candidate if cnt > 1 and cnt == sorted_candidate[0][1]] # 가장 첫 번째(주문 수 가장 많은 것) 주문수와 같으면 answer에 더하기
        
    answer.sort()
                
    return answer

 

배운것

Counter라이브러리 사용법을 배웠다. (복습)⭐️

from collections import Counter

>>> Counter(["hi", "hey", "hi", "hi", "hello", "hey"])
Counter({'hi': 3, 'hey': 2, 'hello': 1})

이렇게 Counter 생성자에 배열을 인자로 넘기면 각 원소가 몇 번씩 나오는지 저장된 객체를 얻을 수 있다.

출력 순서도 값이 큰것부터 내림차순으로 나온다.

>>> Counter("abbcccdddd")
Counter({'d':4, 'c':3, 'b':2', 'a':1})

만약 Counter 객체에 문자열을 인자로 넘기면 각 문자가 문자열에서 몇 번씩 나타나는지를 알 수 있는 객체를 얻을 수 있다.

 

# 1. 상위요소 반환 : most_common()
# most_common() 메서드를 사용하면 인자만큼 상위요소를 출력할 수 있다. 인자를 주지 않으면 전체 요소가 출력

>>> Counter('abbcccddddaaaa').most_common(1) # 상위요소 하나 출력
[('a', 5)]

>>> Counter('abbcccddddaaaa').most_common(2) # 상위요소 두개 출력
[('a', 5), ('d', 4)]

 

위 코드에서 왜 sorted_candidate = Counter(candidates) 를 해주지 않고 

sorted_candidate = Counter(candidates).most_common() 이걸 써줬나 봤더니

뒤에 most_common()을 붙여줘야 배열을 얻을 수 있다.

 

sorted_candidate = Counter(candidates)

print(sroted_candidate)

[('AD', 3), ('CD', 3), ('AB', 2), ('AC', 2), ('AE', 2), ('DE', 2), ('XY', 2), ('XZ', 2), ('YZ', 2), ('BC', 1), ('BD', 1), ('BE', 1), ('CE', 1)]
[('ACD', 2), ('ADE', 2), ('XYZ', 2), ('ABC', 1), ('ABD', 1), ('ABE', 1), ('ACE', 1), ('BCD', 1), ('BCE', 1), ('BDE', 1), ('CDE', 1)]
[('ABCDE', 1)]

 

sorted_candidate = Counter(candidates).most_common()

print(sorted_candidate)

Counter({'AD': 3, 'CD': 3, 'AB': 2, 'AC': 2, 'AE': 2, 'DE': 2, 'XY': 2, 'XZ': 2, 'YZ': 2, 'BC': 1, 'BD': 1, 'BE': 1, 'CE': 1})
Counter({'ACD': 2, 'ADE': 2, 'XYZ': 2, 'ABC': 1, 'ABD': 1, 'ABE': 1, 'ACE': 1, 'BCD': 1, 'BCE': 1, 'BDE': 1, 'CDE': 1})
Counter({'ABCDE': 1})

 

새롭게 배운 Counter 클래스는 나중에 유용하게 써먹을 수 있을 것 같다.

복습하자 복습!