2021 KAKAO BLIND_ 메뉴 리뉴얼

문제

문제는 다음과 같다

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

입력

• orders: 각 손님들이 주문한 단품메뉴들이 문자열 형식으로 담긴 배열
• course: 추가하고 싶어하는 코스요리를 구성하는 단품메뉴들의 갯수가 담긴 배열

출력

새로 추가하게 될 코스요리의 메뉴 구성을 문자열 형태로 담은 배열

• 알파벳순으로 정렬되어있어야함

접근 방법

처음엔 교집합을 이용해서 풀려고 했다.
먼저 orders를 내부 문자열의 길이를 기준으로 sort하고
길이가 작은 order부터 차례로 훝으며 그 뒤에 있는 order 중 교집합인 원소들을
담고 담고하면서 겹치는 메뉴들을 count하는 방법을 생각했다.

하지만 문제가 있다는 걸 깨닫고 다시 문제를 정독했다.
orders의 원소 order를 n, course의 원소 c를 r이라고 보는건 어떨까?
$nCr$을 한다고 생각해보자.

orders : ["ABCFG", "AC", "CDE", "ACDE", "BCFG", "ACDEH"]

이때 order(= for in orders)에서 combination r 하면
order에 대한 r개의 조합을 모두 구할 수 있다.
그 결과들을 dictionary에 넣고 count하면서 orders를 순회하고 끝나면 course를 순회하면서 모든 조합의 경우의 수와 그에 대한 count를 담은 dictionary를 구한다.

그 코드는 아래와 같다.

import itertools

def solution(orders, course):
    answer = []
    # n_C_r
    dic_course = dict()
    while course:
        r = course.pop(0)
        
        for order in orders:
            if len(order) >= r:
                for _course in list(itertools.combinations(order, r)):
                    _course = tuple(sorted(list(_course)))
                    if _course not in dic_course:
                        dic_course[_course] = 1
                    
                    else:
                        dic_course[_course] += 1
       

위 코드를 실행해서 만들어진 dic_course를 출력하면 다음과 같다.

count가 다 완료되기 전까지 중복된 메뉴의 수가 2 이상이여야 한다는 문제의 조건을 체크할 수 없었기때문에 값이 1인것도 포함되어 있다.

dic_course 중 key의 길이별로 value가 제일 큰 key를 구해야 하기 때문에
먼저 len(key)(오름차순)와 value(내림차순)로 정렬해주었다.

다음과 같다.

dic_course = sorted(dic_course.items(), key = lambda x : (len(x[0]), -x[1]))

그 다음 dic_course를 순회하면서 answer에 해당되는 key를 찾고 찾으면 sort하고 string type으로 변환 후 answer에 삽입해줬다. 이런 방식으로 dic_course를 순회하며 answer의 원소들이 모두 채워지면 sorted(answer)를 return한다.
코드는 아래와 같다.

now_len = len(dic_course[0][0])
max_cnt = dic_course[0][1]

for key , val in dic_course:
    if val == 1: continue
    if len(key) > now_len:
        max_cnt = val
        now_len = len(key)
        answer.append("".join(sorted(list(key))))
    
    elif len(key) == now_len:
        if max_cnt == val:
            answer.append("".join(sorted(list(key))))
        
    answer = sorted(answer)
                    
    return answer

전체 코드

import itertools


def solution(orders, course):
    answer = []
    # 조합이라니...
    # n_C_r
    dic_course = dict()
    while course:
        r = course.pop(0)

        for order in orders:
            if len(order) >= r:
                for _course in list(itertools.combinations(order, r)):
                    _course = tuple(sorted(list(_course)))
                    if _course not in dic_course:
                        dic_course[_course] = 1

                    else:
                        dic_course[_course] += 1

    dic_course = sorted(dic_course.items(), key=lambda x: (len(x[0]), -x[1]))
    # print(dic_course)

    now_len = len(dic_course[0][0])
    max_cnt = dic_course[0][1]

    for key, val in dic_course:
        if val == 1: continue
        if len(key) > now_len:
            max_cnt = val
            now_len = len(key)
            answer.append("".join(sorted(list(key))))

        elif len(key) == now_len:
            if max_cnt == val:
                answer.append("".join(sorted(list(key))))

    answer = sorted(answer)

    return answer