[알고리즘] 메뉴 리뉴얼 python (프로그래머스)

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

프로그래머스

이번 글에서는 Python을 사용해 코딩 테스트 문제를 해결한 방법을 공유합니다. 문제는 특정 고객 주문 기록을 바탕으로 가장 자주 등장하는 단품 메뉴 조합을 찾아 코스요리 메뉴로 구성하는 것입니다. 이 과정에서 itertools 모듈의 combination와 lambda 정렬 함수를 활용해 해결했습니다. 문제 풀이와 함께 코드의 각 부분을 자세히 설명하겠습니다.

---

문제 요약

1. 여러 손님이 단품 메뉴를 조합해 주문합니다.
2. 특정 개수의 단품 메뉴를 조합해 가장 자주 등장하는 메뉴 조합을 코스 요리 메뉴로 구성합니다.
3. 메뉴 조합은 최소 2명 이상의 손님에게 주문된 조합만 후보에 포함됩니다.
4. 코스 요리 메뉴는 사전순(알파벳순)으로 정렬해 반환해야 합니다.

입력 예시

orders = ["ABCFG", "AC", "CDE", "ACDE", "BCFG", "ACDEH"]
course = [2, 3, 4]

---

문제 풀이 과정

1. itertools.combinations로 모든 메뉴 조합 생성

손님들이 주문한 메뉴에서 가능한 모든 조합을 찾아 몇 번 주문됐는지 카운트합니다. 이때 **itertools.combinations**를 사용하면 모든 조합을 쉽게 생성할 수 있습니다.

• *itertools.combinations(order, n)*은 길이가 n인 모든 조합을 만들어줍니다.

예를 들어 "ABCFG"에서 길이가 2인 조합은 다음과 같습니다.

('A', 'B'), ('A', 'C'), ('A', 'F'), ('A', 'G'), ('B', 'C'), ('B', 'F'), ('B', 'G'), ('C', 'F'), ('C', 'G'), ('F', 'G')

이 조합들을 모두 문자열로 변환해 딕셔너리에 저장하고, 등장 횟수를 카운트합니다.

for order in orders:
    for combinationCount in course:
        for elements in itertools.combinations(order, combinationCount):
            d["".join(elements)] += 1

• order는 각 손님의 주문 내역을 알파벳순으로 정렬합니다.
• combinations(order, combinationCount)는 현재 주문에서 특정 길이(combinationCount)만큼의 모든 조합을 생성합니다.
• d["".join(elements)]는 딕셔너리 d에 조합 문자열을 키로 사용해 등장 횟수를 기록합니다.

---

2. 최다 주문 조합 추출

이제 특정 길이의 조합 중 최대 주문 횟수를 구해 해당 조합을 결과에 추가합니다.

딕셔너리 d에 저장된 각 조합을 순회하며 다음 조건을 확인합니다.

• 주문 횟수가 2번 이상일 것
• 같은 길이의 조합 중 가장 많이 주문된 조합일 것

이 과정에서 lambda 정렬을 활용합니다.

for key, value in sorted(d.items(), key=lambda x: [-x[1], -len(x[0]), x[0]]):
    visitedKey = len(key)
    if value > 1 and visited[visitedKey] <= value:
        visited[visitedKey] = value
        res.append(key)

정렬 기준은 다음과 같습니다.

• x[1]: 등장 횟수를 내림차순 정렬합니다. 가장 많이 등장한 조합이 먼저 나오도록 합니다.
• len(x[0]): 조합의 길이를 내림차순 정렬합니다. 같은 등장 횟수라면 더 긴 조합이 먼저 나오게 합니다.
• x[0]: 최종적으로 조합을 알파벳순으로 정렬합니다.

예시

정렬 기준이 적용된 딕셔너리 d의 값이 다음과 같다고 가정합시다.

[("AC", 4), ("CDE", 2), ("BCFG", 2), ("ACDE", 2)]

정렬 과정은 다음과 같습니다.

1. 등장 횟수 기준 내림차순: AC(4), CDE(2), ACDE(2), BCFG(2)
2. 같은 등장 횟수일 때는 조합 길이 기준 내림차순 정렬
3. 마지막으로 알파벳순 정렬

결과는 최종적으로 ["AC", "CDE", "BCFG", "ACDE"]가 반환됩니다.

---

최종 코드

전체 코드는 다음과 같습니다.

import itertools
import collections

def solution(orders, course):
    orders = list(map(lambda x: sorted(x), orders))
    d = collections.defaultdict(int)

    # 모든 조합의 등장 횟수 카운트
    for order in orders:
        for combinationCount in course:
            for elements in itertools.combinations(order, combinationCount):
                d["".join(elements)] += 1

    visited = {ind: 0 for ind in course}
    res = []

    # 최다 주문 조합 찾기
    for key, value in sorted(d.items(), key=lambda x: [-x[1], -len(x[0]), x[0]]):
        visitedKey = len(key)
        if value > 1 and visited[visitedKey] <= value:
            visited[visitedKey] = value
            res.append(key)

    return sorted(res)

---

정리

• itertools.combinations를 사용해 가능한 모든 조합을 구하고 등장 횟수를 카운트했습니다.
• lambda 정렬을 통해 등장 횟수, 조합 길이, 알파벳순을 기준으로 최적의 코스 요리 조합을 추출했습니다.
• 정렬 기준을 명확히 이해하고 응용하면 다양한 문제에서 효율적인 코드를 작성할 수 있습니다.