프로그래머스 메뉴 리뉴얼 문제 풀러 가기

문제 설명

나의 노력의 흔적 ...

from collections import defaultdict
def solution(orders, course):
    arr = []
    d = defaultdict(int)
    for i in range(len(orders)-1):
        for j in range(i+1, len(orders)):
            first, second = orders[i], orders[j]
            for _ in range(2):
                    arr.append(''.join(set(first)&set(second)))
    
    arr = [elem for elem in arr if elem != '']
    for elem in arr:
        d[elem] += 1
    
    print(arr)
    print(d)
    key = list(d.keys())
    for i in range(len(key)-1):
        for j in range(i+1, len(key)):
            if key[i] in key[j]:
                d[key[i]] += 1
            elif key[j] in key[i]:
                d[key[j]] += 1
    print(d)
    return 0

완전탐색을 돌면서 주문 간 겹치는 메뉴를 찾고 개수를 세려고 했다.
하지만, 아래와 같은 두 가지 문제에 맞닥뜨려 결국 다른 사람의 풀이를 참고하여 문제를 풀 수 있었다 🥺

• ABCDE와 AB라는 주문이 있을 때, ABCDE 안에 AB가 있는지 또 검사해야 한다
• XY와 YX를 다른 메뉴로 취급한다

구현 아이디어

입출력 예 2번을 예시로 구현 아이디어를 설명하겠다.

orders: ["ABCDE", "AB", "CD", "ADE", "XYZ", "XYZ", "ACD"]
course: [2,3,5]

1. courses의 숫자만큼 반복한다. (2개짜리 조합, 3개짜리 조합, 5개짜리 조합)
   1-1. 모든 order에 대해 반복한다.
   • order에 대해 course 값만큼의 조합을 구한다. ('ABCDE' → 'AB', 'AC' ...)
   • 'XY'와 'YX'와 같이 순서만 다른 경우를 방지하기 위해 order을 sort해준 후 조합을 구해야 한다.
2. 조합된 주문에 대해 모든 주문 내역에 있는 해당 조합의 갯수를 센다. (counter을 사용)
3. 해당 counter에 아무 값도 없거나(= 해당 주문 조합이 나온 적이 없거나), 최댓값이 1이라면 pass
   • 입출력 예 3번에서 각 주문에 있는 최대 3개인데, course=4인 경우 counter에 아무 값이 없다
   • 최소 2명 이상의 손님으로부터 주문된 단품메뉴 조합에 대해서만 코스요리 메뉴 후보에 포함한다.
4. 그렇지 않다면 answer에 최댓값을 가진 주문 조합을 넣는다.
5. answer을 정렬하여 반환한다.

전체 코드

from collections import Counter
from itertools import combinations

def solution(orders, course):
    answer = []
    for number in course:
        temp = [] # (number)가지 메뉴로 구성된 모든 조합이 저장된다.
        for order in orders:
            c = combinations(sorted(order), number) # 순서만 다른 주문을 방지하기 위해 정렬 후 조합을 구한다
            temp += c
        counter = Counter(temp)
        if len(counter) != 0 and max(counter.values()) != 1:
            answer += [''.join(i) for i in counter if counter[i] == max(counter.values())]
        
    return sorted(answer)

collections 모듈의 Counter

Counter는 데이터의 갯수를 셀 때 유용하게 사용할 수 있는 클래스이다.
dictionary 자료 구조를 확장하고 있어, dictionary에서 제공하는 기능들을 그대로 사용할 수 있다.

Counter 기본 사용법

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

가장 많이 사용된 요소 찾기

print(Counter('abbcccddddaaaa).most_common(1))
# [('a', 5)]

print(Counter('abbcccddddaaaa).most_common(2))
# [('a', 5), ('d', 4)]