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

---

문제설명

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

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

사고과정

• 문제가 DFS 탐색으로 완전탐색을 하는 것이라고 예상했다. 심지어 주어진 문제 범위도 매우 작았다. 처음에 문제에서 얻어지는 조합 개수마다 각 개수에서  '가장 많이 함께 주문된 단품메뉴'를 한 번에 캐치하지 못해서 그냥 단순히 2명의 이상 손님에게 함께 주문된 단품메뉴를 추출한 후 왜 답이랑 다르지? 생각했다. 문제를 다시 읽고 캐치한 후 구현에 성공했다!
• 크게 보면 DFS 탐색 + 해쉬를 사용해 풀이였다. DFS로 각 손님이 주문한 단품메뉴 조합에서 주어진 course 배열 loop를 돌면서 2개, 3개, 4개 조합을 완전탐색했다. 단, 이 때 구한 조합을 해쉬에 키 값으로 넣어주면서 카운트를 해주어야 하는데, 주의해야 할 점은 구한 조합을 알파벳 순서대로 정렬한 후 넣어주는 것이 중북된 key값으로 넣어지지 않고 동일한 key로 인식한 후 카운트를 해준다. 이는 문제에서 입출력 예시 3번을 보면 된다. 문제에서 WX가 result 리스트에 존재하는데, 문제에서 주어진 orders 에는 [XYZ, XWY, WXA] 가 있다. 즉, XW 도 WX로 인식하도록 해주어야 한다는 것! 이를 구현하기 위해 조합을 찾은 뒤 해쉬에 넣어주기 전에 조합을 사전 순으로 정렬한 후 해쉬에 넣어주면서 해결했다!
• 시간이 꽤 오래 걸렸던 문제였다.. 하루종일 걸리더라도 어떻게든 풀이하자는 생각으로 풀었다. 다행히 구현에 성공했다!(이게 레벨 2라니...갈 길이 멀다..)

풀이

def dfs(L, s, order, res, arr):
    if L == len(res):
        tmp = ''.join(sorted(res))
        arr[tmp] = arr.get(tmp, 0) + 1
        return
    else:
        for i in range(s, len(order)):
            res[L] = order[i]
            dfs(L+1, i+1, order, res, arr)


def solution(orders, course):
    arr = {}
    
    for order in orders:
        # 각 order 마다 각 course의 길이 조합 구하기
        for length in course:
            res = [0] * length
            dfs(0, 0, order, res, arr)
    
    result = [0] * (max(course)+ 1) # order 길이 별 최대 개수 저장
    
    for k, v in arr.items():
        if v >= 2:
            result[len(k)] = max(result[len(k)], v)
    
    answer = []
    for k, v in arr.items():
        if v == result[len(k)]:
            answer.append(k)
    return sorted(answer)