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

프로그래머스 문제 정복기

 

난이도 : lv2

---

🔗 Link

---

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

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

 

 

📑 Summary

---

  주문 내역인 orders와 courses가 주어진다. courses는 단품 메뉴들의 개수를 담은 배열이다. course가 2라면, 2개의 단품 메뉴로 구성된 메뉴이다. course의 개수에 따라 코스 메뉴를 구성할 때, 각 course는 가장 많이 주문 된 상품의 조합으로 하려고 한다. orders와 주어진 courses를 이용하여, 만족하는 상품의 조합들을 출력하는 문제이다.

(아따따... 문제 요약하기도 어렵다)

 

🔑 How to solve? 

---

 문제는 대놓고 상품들의 조합을 이야기하고 있다. 즉, 조합의 이야기 이다. 나는 코테를 풀 때, 문제를 보고 조합으로 풀만한 문제가 있나 한 번쯤 둘러보는 편인데, 그 이유는 조합에서는 파이썬이 강점이 있기 때문이다. (필자는 보통 자바로 풀지만, 경우에 따라 파이썬으로 풀기도 한다.) 파이썬의 itertools 모듈에는 순열(permutations)과 조합(combinations)을  쉽게 만들어주는 함수가 존재하기 때문에 시간을 많이 줄일 수 있다. 이야기가 좀 산으로 갔는데, 다시 문제로 돌아가 보자.

 

해당 문제는 특정 코스요리 개수에서 가장 인기가 많은 상품 조합을 뽑아내는 문제다. 해당 문제를 풀기 위해 무엇을 먼저 해야 할지 생각해보자. 문제가 복잡한 듯 하지만, 글로 써보면 생각보다 우리가 해야 할 일들은 간단하다. 

 

문제에서 요구하는 목적은 각 코스에서 가장 인기 있는 상품 조합들을 반환하는 것이다. 이 문장에서 어느 정도 해결책이 나와있다. 각 코스이므로 코스별로 구별을 해야 하고, 인기 있는 상품을 고르는 방법을 구현하면 된다. 그렇다면 순서는 누가 먼저 되어야 할까?

 

💡코스별로 생각해야 하는 이유

 쉽고 빠르게 비교하기 위해서는 고정된 제약조건이 많아야 편하다. 각 주문당 요구하는 모든 코스의 조합을 먼저 꺼내서 비교한다면, 코스의 개수가 맞는 것들끼리 구별하기가 쉽지 않다.(이 자체가 조건문이 추가되기 때문이다.) 그렇기 때문에 같은 조합을 가진 코스의 요리들을 모아서 가장 주문이 많은 상품군을 선택해야 한다. 그렇게 선택된 것들을 모아서, 문제가 요구하는 정렬에 맞게 반환해야 한다. 정리하자면, 다음과 같다. 

 

1. 코스별로 생각하자
2. 코스별로 어떻게 가장 인기 있는 상품을 선택할 것인지 생각하자
3. 결과를 어떻게 정렬해야 할지 생각하자.

코스별로 생각하자🔖

 코스별로 생각하는 것은 쉽다. 반복문을 이용하여 코스를 먼저 나누자

 

코스별로 어떻게 가장 인기 있는 상품을 선택할 것인지 생각하자🔖

 해당 문제에서 오답이 나왔다면, 아마 가장 많이 구현에 어려움을 느낀 부분이 이 부분이었을 확률이 높다.  우선 가장 인기 있다는 것은 각 주문에서 가장 많이 주문된 상품 조합이라는 의미이다. 그렇다면, 우선적으로 코스별로 나올 수 있는 모든 조합을 다 구해봐야 한다. 이러한 조합을 combinations 함수를 이용하여 사용한다면 쉽게 구할 수 있다.

 

예를 들어, course가 2라면, 1번째 order에서 2개로 만들 수 있는 상품군의 모든 조합의 수부터 마지막 order에서 2개로 만들 수 있는 상품군의 모든 조합의 수를 구한다. 그다음, 각 주문에서 해당 상품군이 있는지 없는지 확인한다면, 가장 많이 주문된 상품군을 구할 수 있다.

 

Q1. 순서쌍은 맞지만, (B, A)와 (A, B) 같이 위치가 바뀐 경우를 어떻게 처리하나요?

 이 부분은 집합의 개념을 이용한다면, 간단하게 넘어갈 수 있다. set 자료용을 이용함으로써, 중복에 대해 신경 쓰지 않아도 되고, 순서쌍에 대해서도 걱정할 필요가 없다.

 

Q2. 각 주문에 해당 상품이 있는지 판단하는 논리를 코드로 만들기 어려워요

 주문에서 해당 상품군이 있다는 것은 해당 상품군이 그 주문의 부분집합이라는 의미이다. 해당 함수를 이용하기 위해선 각 주문과 상품군을 set 자료형을 이용하여 집합으로 만들어 주어야 한다.  상품군이 해당 주문에 부분집합이라는 의미는 상품군 자체가 해당 주문에 대해 교집합임을 이용한다면 쉽게 풀 수 있다. ( & or intersection() 함수를 이용하면 된다.)

 

정리를 하자면, 각 주문에서 해당 course개의 상품군으로 구성된 모든 조합을 구하여, 각 주문과 비교한다. 그중에서 가장 인기 있는 메뉴를 선정한다.

 

※ 문제에서는 주문된 수가 같다면, 여러 개를 반환해야 하는 점을 꼭 염두하고 코딩하자.

 

 

결과를 정렬하기🔖

 문제는 알파벳 순으로만 요구하고 있으므로, 결과를 리스트에 담고 정렬 한번 해주면, 알파벳순으로 잘 정렬된다. 

 

 

💡 Code

---

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

import itertools
def solution(orders, course):
    answer = []
    #각 코스별로 계산
    for cnt in course:
        #각 주문당 나올 수 있는 조합을 담기 위한 변수
        targets=[]
        #주문별로 나눠서 생각
        for order in orders:
            # 해당 주문에서 course개의 상품을 고를 수 있는 조합의 수 
            for target in list(itertools.combinations(set(order),cnt)):
                targets.append(target)

        #가장 인기 있는 메뉴 선정
        results = getMaxMenu(orders,targets)
        
        #인기 메뉴가 여러개 일 수 있으므로 for문을 통해 결과에 삽입
        for result in results:
            answer.append(result)

    answer.sort()
    return answer

#조합의 경우를 주문과 비교하여 가장 인기있는 메뉴를 반환하는 함수
def getMaxMenu(orders,targets):

    result =dict()
    for target in targets:
        target = set(target)
        cnt = 0
        
        for order in orders:
            order = set(order)
            #해당 target이 주문의 부분집합인지 판단 
            if target == order& target:
                cnt+=1

        if cnt > 1 :
            target = list(target)
            target.sort()
            result[''.join(target)]= cnt

    
    #가장 인기 있는 메뉴의 key값(상품 명)을 저장
    output = [keys for keys,v in result.items() if max(result.values())== v  ]
    #반환
    return output

 

 

 

---

포스팅에 문제가 있거나, 설명이 잘못된 부분 지적 환영합니다.

더 나은 퀄리티의 콘텐츠를 제공할 수 있도록 노력하겠습니다.

읽어주셔서 감사합니다.