[PG72411] 메뉴 리뉴얼

프로그래머스

🚩 문제 설명

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

코딩테스트 연습 - 메뉴 리뉴얼

PG72411

⏱️ 시간 복잡도
▪ 각 문자열의 조합을 구한다고 한다면
▪ orders의 크기를 N, orders의 문자열의 크기를 M, course의 크기를 K라고 가정하자.
▪ 대략적인 시간복잡도는 O(NMK) 라고 할 수 있다.
▪ 애초에 최대 크기가 20, 10 정도 인것으로 보아 반복문이 세번 등장해도 괜찮은 것으로 보인다.

◾ 단품 메뉴를 조합하여 코스 요리 메뉴로 구성한다.

◾ 코스요리 메뉴는 최소 2가지 이상의 단품 메뉴로 구성한다.

◾ 최소 2명의 손님에게 주문된 단품메뉴 구성만 취급한다.

◾ 새로 추가하게 될 코스요리의 메뉴 구성을 문자열로 배열에 담아 출력하는 문제

◾ 즉, 단품 메뉴 구성 중에서 제일 많이 주문된 것을 출력하는 문제이다.

◾ 문제가 많이 헷갈린다. 문제의 이해는 다음과 같다.

orders	조합의 수
XYZ	XY, XZ, YZ, XYZ
XWY	XW, XY, WY, XWY
WXA	WX, WA, XA, WXA

XY	XZ	YZ	WX	WY	AW	AX	XYZ	WXY	AWX
2	1	1	2	1	1	1	1	1	1

◾ 따라서 XY, WX가 해답이 된다.

◾ 조합도 알파벳 오름차순으로, 출력하는 배열도 알파벳 오름차순으로 출력해야 한다.

 

 

 

---

 

 

 

✅ 입출력

orders : 각 손님마다 주문한 단품메뉴들
course : 코스요리로 구성 가능한 단품메뉴 갯수들
return ➡️ 새로 추가하는 코스요리의 메뉴 구성 문자열로 담아 배열로 반환

orders	course	return
["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"]

 

 

 

---

 

 

 

📑 문제 풀이

with 파이썬 (Python)

from itertools import combinations


def solution(orders, course):
    ans = []
    cdts = {}

    # 후보군 만들기
    for c in course:
        for o in orders:
            cdt = list(combinations(o, c)) # 조합
            for i in cdt:
                cdts[''.join(sorted(i))] = 0

    # 주문 횟수 세기
    for cdt in cdts:
        for o in orders:
            if set(list(cdt)).issubset(set(list(o))):
                cdts[cdt] += 1

    # 주문 2번 미만 탈락
    cdts_ = []
    for k, v in cdts.items():
        if v >= 2:
            cdts_.append((k, v))

    # 최댓값
    possible = []  # 각 코스 갯수에 따른 메뉴 후보군
    possible_ = []
    for c in course:
        for k, v in cdts_:
            if len(k) == c:
                possible.append((k, v))
            else:
                continue
        possible = sorted(possible, key=lambda x: x[1], reverse=True)

        if possible:  # max 값 골라내기
            max_ = possible[0][1]

        for p in possible:  # 최종 값 골라내기
            if p[1] == max_:
                possible_.append(p)
        possible = []

    # 답안 출력
    possible_ = sorted(possible_)
    for a in possible_:
        ans.append(a[0])

    return ans

➕ 다른 사람 풀이

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) ]

💬 Point

➡️  collections의 combinations 사용 (조합)
➡️  set().issubset() 사용 (집합)
➡️  value를 기준으로 오름차순 sorted 사용
➡️  max 값을 골라내서 max랑 값이 같은 것들만 배열에 추가하여 출력한다.

◾ 우선 조합을 사용하여 후보군을 만들어준다.

• AB, AC, ... 이런식의 후보군을 만들어주는 과정.
• 후보군의 갯수는 course의 요소로 결정된다.
• orders[i] C course[j]

◾ 만든 후보군들이 얼마나 orders에서 얼마나 언급이 되는지 갯수를 세준다.

• set(리스트 A).issubset(집합 B) 함수를 사용하면 해당 집합 B에 A 집합을 포함하는 지 알 수 있다.

◾ 최소 두명 이상 주문한 단품메뉴구성만 후보에 추가하므로 2 미만은 제외한다.

◾ 각 코스의 갯수대로 max 값을 구해준다.

◾ max랑 값이 같은 요소들만 배열에 추가한다. (공동순위를 뽑아내는 과정)

◾ 정렬하려 반환한다.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

# 프로그래머스 메뉴 리뉴얼 파이썬

# 프로그래머스 메뉴 리뉴얼

---