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

2022 KAKAO BLIND RECRUITMENT

• Lv 2. 메뉴 리뉴얼 (Python)
  https://school.programmers.co.kr/learn/courses/30/lessons/72411

Code

from itertools import combinations

def solution(orders, course):
    answer = []

    # 가장 많이 주문한 단품을 -> 코스요리로 구성
    # 코스요리 : 최소 2개 이상의 단품
    # 최소 2명 이상의 손님으로부터 주문된 단품이 코스요리 후보

    ### 가장 많이 주문된 단품메뉴 조합 구하기 (pick_num 개수 만큼 뽑은 조합)
    def get_course(pick_num):
        max_list = set()    # 가장 많이 주문된 단품메뉴 조합을 담을 set()

        # 각 손님이 주문한 메뉴를 기반으로 pick_num만큼 뽑아서 만들 수 있는 조합 모두 check_list에 담기
        check_list = list()
        for i in range(len(orders)):
            arr = list(combinations(orders[i], pick_num))
            for j in range(len(arr)):
                check_list.append(arr[j])

        # orders를 순회하며 check_list에 들어있는 각 조합의 개수가 몇번 주문되었는지를 카운트해서 담을 배열
        find_course = [0 for _ in range(len(check_list))]

        for i in range(len(check_list)):            # ('F', 'G')
            for n in range(len(orders)):            # 'ABCFG'
                flag = True
                for j in range(len(check_list[i])):  # 'F'
                    if (check_list[i][j] not in orders[n]):     # 해당 조합의 요소가 들어있지 않는 주문이라면 flag = False
                        flag = False
                        break
                if (flag):
                    find_course[i] += 1

        if (find_course):   # find_course가 비어있지 않으면 max값 구해서 최대로 주문된 개수의 조합을 max_list에 담기
            get_max = max(find_course)

            if (get_max >= 2):
                for i in range(len(find_course)):
                    if (find_course[i] == get_max):
                        max_list.add(tuple(sorted(check_list[i])))

        return max_list

    ### 정답 구하는 부분
    for i in range(len(course)):
        pick_num = course[i]    # 코스요리를 구성하는 단품메뉴의 개수

        c = get_course(pick_num)    # 해당 개수의 단품메뉴 조합 중 가장 많이 주문된 조합의 set()
        c = list(c)     # set()을 리스트로 변환

        # 정답 배열에 추가하는 과정
        for p in range(len(c)):
            ans = ''
            for q in range(len(c[p])):
                ans += c[p][q]      # 쪼개져있는 문자열 합치기
            answer.append(ans)

    answer = sorted(answer)     # 오름차순 정렬

    return answer

if __name__ == '__main__':
    print(solution(["ABCFG", "AC", "CDE", "ACDE", "BCFG", "ACDEH"], [2,3,4]))
    # ["AC", "ACDE", "BCFG", "CDE"]

    print(solution( ["ABCDE", "AB", "CD", "ADE", "XYZ", "XYZ", "ACD"], [2, 3, 5]))
    # ["ACD", "AD", "ADE", "CD", "XYZ"]

    print(solution(["XYZ", "XWY", "WXA"], [2, 3, 4]))
    # ["WX", "XY"]

    print(solution(["ABCD", "ABCD", "ABCD"], [2,3,4]))
    # ['AB', 'ABC', 'ABCD', 'ABD', 'AC', 'ACD', 'AD', 'BC', 'BCD', 'BD', 'CD']

풀이 및 해설

• 우선 문제가 조금 헷갈리게 써있기는 한데 핵심은 이것
  • course에 따른 수가 [2, 3, 4] 라면
    2개씩 뽑기 → 그 중 가장 많은 개수를 가진 조합이 코스요리가 됨
    3개씩 뽑기 → 그 중 가장 많은 개수를 가진 조합이 코스요리가 됨
    4개씩 뽑기 → 그 중 가장 많은 개수를 가진 조합이 코스요리가 됨
• check_list에는 각 손님이 주문한 음식 구성에서 pick_num 만큼 뽑을 수 있는 모든 조합을 담아놓는다.
  • check_list에 담겨있는 값의 예시 ⇒ [('A', 'B'), ('A', 'C'), ('A', 'F'), ('A', 'G'), ('B', 'C'), ('B', 'F'), ('B', 'G'), ('C', 'F'), ('C', 'G'), ('F', 'G'), ('A', 'C'), ('C', 'D'), ('C', 'E'), ('D', 'E'), ('A', 'C'), ('A', 'D'), ('A', 'E'), ('C', 'D'), ('C', 'E'), ('D', 'E'), ('B', 'C'), ('B', 'F'), ('B', 'G'), ('C', 'F'), ('C', 'G'), ('F', 'G'), ('A', 'C'), ('A', 'D'), ('A', 'E'), ('A', 'H'), ('C', 'D'), ('C', 'E'), ('C', 'H'), ('D', 'E'), ('D', 'H'), ('E', 'H')]
    
• find_course에는 check_list의 각 조합의 개수가 각 손님이 주문한 음식 구성 안에 얼마나 들어있는지를 세서 해당 인덱스에 더해놓는다.
  • find_course에 담겨있는 값의 예시 ⇒ [1, 4, 1, 1, 2, 2, 2, 2, 2, 2, 4, 3, 3, 3, 4, 2, 2, 3, 3, 3, 2, 2, 2, 2, 2, 2, 4, 2, 2, 1, 3, 3, 1, 3, 1, 1]
    
• 최소 2명 이상이 주문했던 조합이어야 코스요리가 될 수 있기 때문에, find_course에서 max값을 구했을 때 2가 넘지 않으면 해당 pick_num으로 만든 조합에서는 코스요리를 만들 수 없다.
• find_course의 max값을 기반으로 해당 배열을 돌면서 max값을 가진 인덱스의 check_list를 저장해주면 가장 많은 개수를 가진 조합을 알 수 있다.
  • 위 두개의 예시라면, ⇒ max값이 4
    만약 find_course[i]가 4라면, check_list[i] 저장 → ('A', 'C')
    
  • 중복을 없애기 위해 set()로 저장해주고 return한다.
• max_list.add(tuple(sorted(check_list[i])))
  • 이렇게 정렬 → 리스트가 됨 → 튜플로 바꿈 → set()에 add 하는 이유 ⇒ set()에 추가하기 위해서는 tuple형식이어야 하나, ‘XY’, ‘YX’ 가 같은 조합인걸 판단하기 위해서는 정렬 후 set()에 추가해주어야 한다.
    그러나 정렬하게 되면 리스트화되어 다시한번 튜플로 바꿔줘야 한다 !~
    

What I learned

• collections.Counter()를 사용하면 훨씬 더 간단해진다 … ㅋㅋ 또 까먹었네 !

import collections
import itertools

def solution(orders, course):
    result = []

    for course_size in course:
        order_combinations = []
        for order in orders:
            order_combinations += itertools.combinations(sorted(order), course_size)

        most_ordered = collections.Counter(order_combinations).most_common()
        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) ]