[Level 2] 메뉴 리뉴얼

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

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

---

접근

가능한 코스의 조합을 생성하여 딕셔너리에 넣고 카운트하는 방법으로 접근하고자 했다. 하지만 시간초과가 발생할 것 같았다. 최대 10개의 course가 들어오는데 각각의 조합을 만들 때 시간이 많이 걸릴 것 같았지만 시도를 해보았다.

 

먼저 course에 있는 순서대로 코스를 구성해본다. 

각각의 수에 맞는 메뉴가 포함된 코스의 경우의 수를 생성하고 딕셔너리에 키로 저장한다. 만약 키가 존재한다면 기존의 값을 증가시키고 없다면 키를 넣고 1로 초기화해준다.

이후 값이 가장 큰 키를 찾고 해당 키를 answer에 추가하는 식으로 구성하였다.

 

결론적으로 시간초과가 발생하지 않았다.

시간 복잡도 계산에 대해 더 공부할 필요가 있다.

 

구현

입력된 orders의 각 문자열을 리스트의 형태로 order_list에 추가하였다.

이후 course에 있는 수를 순서대로 꺼내서 해당 c만큼의 메뉴가 포함된 코스를 생성한다.

코스가 될 수 있는 경우의 수를 생성할 때는 itertools에 있는 combinations를 사용했다.

가능한 조합을 생성한 뒤에 문자열로 변경하고 combies라는 리스트에 추가한다.

이후 order_dict라는 딕셔너리에 키를 추가한다.

cmobies 탐색을 종료했을 때 딕셔너리가 비어있다면 다음으로 넘어가며 그렇지 않았을 때 최댓값을 찾는다.

먼저 value 중 최댓값을 담아 max_val에 담고 이 값이 2 이상일 때 최댓값을 갖는 key를 검사하여 answer에 추가한다.

 

최종적으로 answer을 오름차순으로 정렬하여 반환한다.

from itertools import combinations


def solution(orders, course):
    answer = []
    order_list = []
    for order in orders:
        order_list.append(list(map(str, order)))

    for c in course:
        order_dict = {}
        for order in order_list:
            
            combies = list(map(''.join, list(combinations(sorted(order), c))))

            for combi in combies:
                if combi in order_dict:
                    order_dict[combi] += 1
                    continue
                order_dict[combi] = 1
        if len(order_dict) == 0:
            continue
        max_val = max(order_dict.values())
        if max_val >= 2:
            for key, value in order_dict.items():
                if value == max_val:
                    answer.append(key)

    answer = sorted(answer)

    return answer

 

다른 사람의 코드

풀고나서 다른 사람들의 코드를 보고 더 간결하게 작성해보았다.

나는 orders를 리스트로 변환하여 사용했지만 문자열 자체에서 조합을 생성할 수 있었다. 

이후 collections의 Counter를 통해 조합에 대해 수를 카운트하고 most_common()을 통해 내림차순으로 정렬하여 max_order에 담았다.

그리고 최댓값을 찾아 문자열로 만들어주고 answer에 추가하는 식이다.

from itertools import combinations
from collections import Counter

def solution(orders, course):
    answer = []  

    for c in course:
        order_list = []
        for order in orders:
            
            order_list += combinations(sorted(order), c)

        max_order = Counter(order_list).most_common()
        for key, value in max_order:
            if value > 1 and value == max_order[0][1]:
                answer.append(''.join(key))
    answer = sorted(answer)
    return answer