[프로그래머스] 2021 카카오 공채 - 메뉴 리뉴얼 (파이썬) 문제 및 풀이

문제) 프로그래머스 - 2021 카카오 공채 - 메뉴 리뉴얼

-> programmers.co.kr/learn/courses/30/lessons/72411

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

 

① 나의 풀이

orders 배열에 저장된 단품 메뉴에서 코스 메뉴로 정할 수 있는 모든 조합을 구한다. 이때, 조합을 구해 그 조합의 길이가 course 배열에 들어 있다면 딕셔너리(possible)에 추가한다. 딕셔너리에서 우리는 코스 메뉴의 길이별로 최대를 구해야 한다. 따라서 배열의 인덱스를 course의 길이만큼 만들어 각 배열에 딕셔너리를 선언한다.

 

 

그 후 최소 두 명 이상의 손님으로부터 주문된 단품 메뉴 조합에 한해서만 코스요리 메뉴 후보에 포함되므로 최대가 1인 경우를 제외해서 answer 배열에 추가해준다. 마지막으로 answer 배열을 정렬하면 답을 구한다.

 

⊙반성

귀신에 홀린 듯, 백트래킹에 미쳐있었다. 백트래킹의 테크닉은 "조건이 만족할 때, 모든 조합의 수를 살펴보는 것(완전 탐색)"이다. 문제는 최소 2가지 이상의 단품 메뉴로 구성되고(조건 1) 최소 2명 이상의 손님으로부터 주문된(조건 2) 모든 단품 메뉴 조합을 탐색하는 것이므로 백트래킹이 생각났다. 하지만 백트래킹 구현 실력이 부족한 탓에 많은 시간을 들였는데도 불과하고 백트래킹을 이용한 문제 풀이에 실패했다. 

 

 

소스 코드)

from itertools import combinations


def solution(orders, course):
    possible = [{} for _ in range(len(course))]
    for i in orders:                                            #모든 경우 탐색
        for j in range(len(course)):
            for k in list(combinations(sorted(i), course[j])):  #가능한 모든 코스요리 경우 만들기
                temp = ''.join(k)
                if temp in possible[j]:
                    possible[j][temp] += 1
                else:
                    possible[j].setdefault(temp, 1)

    answer = []
    for i in range(len(course)):
        if possible[i] == {}:                                 #단품메뉴를 주문한 손님이 없을 수 있으므로
            continue
        max_num = max(possible[i].values())
        for j in possible[i]:
            if possible[i][j] == max_num and max_num != 1:    #max_num >= 2를 만족해야 2명이 시킨 경우
                answer.append(j)

    return sorted(answer)

 

② 다른 사람 풀이

⊙  내 소스 코드 + 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) ]

 

collections의 Counter은 문자열이나 리스트를 딕셔너리 형태로 정리해 반환해준다. Counter은 딕셔너리보다 편리한 점(most_common() 메서드)이 많아 더 선호된다. Counter을 사용하여 간단하고 빠르게 구현할 수 있으므로 딕셔너리가 불편한 상황이면 떠오르도록 연습하자.

 

 

⊙ C++로 구현한 백트래킹 구현

yjyoon-dev.github.io/kakao/2021/01/30/kakao-menurenewal/

[프로그래머스] 메뉴 리뉴얼 문제 풀이 (2021 카카오 코딩테스트)

백트래킹을 이용한 풀이가 잘 설명되어 있으니 참고하자!

 

③ 배운 점

1. 백트래킹 구현 실력 부족

2. collections의 활용(dict의 사용이 불편하면 떠올리자)