Lv.2 : 메뉴 리뉴얼

👉 문제링크

프로그래머스

---

 

---

🔸 문제 분석 🔸

• 입력된 주문 마다 코스 길이로 만들 수 있는 조합을 찾는다.
• 조합을 딕셔너리에 저장하며 개수를 카운트한다.
• 저장된 조합에서 길이별 최대값을 오름차순으로 반환한다.
  • 최대값이 중복이면 모두 선택한다.

🔸 코드 🔸

def solution(orders, course):
    dic = {}
    def find_str(s, pick, d, j): # 재귀로 문자 조합
        if len(pick) >= d:          # 찾는 길이(d)의 문자가 완성되면
            pick = ''.join(sorted(list(pick))) # 문자열 오름차순 정렬
            if pick in dic:             # 딕셔너리에 저장
                dic[pick] += 1
            else:
                dic[pick] = 0
            return
        
        for i in range(j,len(s)):   # 문자 조합을 위해 재귀
            find_str(s, pick+s[i], d, i+1)

    for c in course: # 문자열 길이
        for i in orders: # 분해 할 문자열
            find_str(i, "", c, 0)

    temp = []
    for c in course: # 문자열 길이별로 딕셔너리를 분해
        temp.append({k:v for k, v in dic.items() if len(k) == c})

    answer = []
    for d in temp:
        for k, v in d.items(): # 길이별 딕셔너리에서 value 최대값의 key를 저장
            if max(d.values()) == v and max(d.values()) != 0:
                answer.append(k)
    return sorted(answer) # 오름차순 반환

🔸 코드 해석 🔸

• 재귀 형식으로 문자 조합을 만들어가며 딕셔너리에 카운트한다.
  • 이때 오름차순 정렬 후 인덱싱한다.
• 문자열 길이별로 딕셔너리를 나눠서 temp 리스트에 저장한다.
• 딕셔너리의 별 value 최대값의 key를 answer 리스트에 저장한다.
• answer를 오름차순 정렬하며 반환한다.

 

🔸 코드 해석 🔸

from collections import defaultdict, Counter
from itertools import combinations

def solution(orders, course):
    
    cntr = defaultdict(Counter) # {2:{'AB': 3, 'CD': 1, ...}, ...}
    
    for order in orders: # 1 : 각 order에 대해 combinations로 가능한 조합 뽑아서 Counter에 저장
        for n in course:
            if n <= len(order):
                cntr[n].update(combinations(sorted(order), n))
            
    answer = []
    
    for n in cntr:
        max_cnt = max(cntr[n].values()) # 2 : order 수에 대해 최대 빈도수 구하기
        if max_cnt > 1:
            # 3 : 2에서 얻은 빈도수랑 같은 콤보세트 구하기
            answer += [''.join(k) for k, v in cntr[n].items() if v == max_cnt]
    
    return sorted(answer) # 4 : 정렬해서 반환

• 딕셔너리를 Counter 형식으로 선언해 사용한다.
  • combinations로 가능한 조합을 뽑아낸다.
  • 딕셔너리에 주문 길이별로 조합을 카운트해 저장한다.
• 딕셔너리에서 value 최대값의 key를 뽑아낸다.
  • 최대값은 자기자신을 세는 경우를 제외하기 위해 1보다 커야한다.
  • combinations에서 튜플 형식으로 쪼개져 나왔기 때문에 join을 사용해 문자열로 합친다.
• 정렬해 반환한다.

---

🔸 end 🔸

• 좀 꼬인 부분이 많아 푸는데 시간이 꽤 걸렸다.
• 그래도 잘 풀었다고 생각했는데 다른 풀이를 보니 현타가 조금 왔다...
  • 조합 찾기를 재귀로 구현했는데 combinations() 함수로 간단하게 사용할 수 있었다.
  • defalutdict()로 특정한 형식(여기서는 Counter)을 지정해서 딕셔너리를 만들 수 있었다.
• 또 다른 풀이를 보니 Counter의 most_common() 을 사용하면 최대값 찾기를 더 줄일 수 있다.
• 직접 구현하며 딕셔너리 분해, 문자열 조합을 생각해 볼 수 있었던 문제였다.
• 재귀를 사용해서 그런지 내 코드와 combinations() 사용 코드의 시간차이가 컸다.