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

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

 

1. 문제 : Link

메뉴를 조합해서 가장 많이 나온 메뉴를 return

 

2. 풀이

combinations와 Counter를 알아야 풀 수 있었던 문제!

 

먼저 단위마다 (for문으로 course돌려준다)

주문을 확인해서 각 주문의 조합을 맞춰주고 join을 통해 문자열로 변경해준다. 

문자열을 모두 저장한 후에는 counter.most common()을 통해 해당 문자열이 얼마나 나왔는지 출력해주고,

답 리스트에 저장할 때 조건을 2회 이상나오면서 가장 많이 나온 cnt의 횟수와 같은 문자열을 저장해주고 sorted하여 return해준다.

 

3. 코드

from itertools import combinations
from collections import Counter
def solution(orders, course):
    answer = []
    for k in course:
        candidates = []
        for order in orders:
            for combi in combinations(order, k):
                combined = ''.join(sorted(combi))
                candidates.append(combined)
        sorted_candidates = Counter(candidates).most_common()
        answer += [menu for menu, cnt in sorted_candidates if cnt > 1 and cnt == sorted_candidates[0][1]]
    return sorted(answer)

import java.util.*;
class Solution {
    
    static HashMap<String,Integer> map; 

    public static void combi(String ord, StringBuilder sb, int idx, int cnt, int cr){
       if(cnt == cr) {
           map.put(sb.toString(),map.getOrDefault(sb.toString(),0)+1);
           return;
        }
        
        for(int i = idx; i<ord.length(); i++){
            sb.append(ord.charAt(i));
            combi(ord,sb,i+1,cnt+1,cr);
            sb.delete(cnt,cnt+1);
        }
    }
    
    public ArrayList<String> solution(String[] orders, int[] course) {
        ArrayList<String> answer = new ArrayList<>();
        
        // 오름차순으로 변경
        for(int i =0;i<orders.length;i++){
            char[] charArr = orders[i].toCharArray();
            Arrays.sort(charArr);
            orders[i] = String.valueOf(charArr);
        }
        
        for(int cor : course){
            map = new HashMap<>();
            int max = Integer.MIN_VALUE;   
            for(String order : orders){
                StringBuilder sb = new StringBuilder(); 
                if(order.length() >= cor)
                    combi(order,sb,0,0,cor);                               
            }
            
            for(Map.Entry<String,Integer> entry : map.entrySet()){
                    max = Math.max(max,entry.getValue());
                   
            }
            for(Map.Entry<String,Integer> entry : map.entrySet()){
                    if(max >=2 && entry.getValue() == max)
                        answer.add(entry.getKey());
            }
        }
        Collections.sort(answer);
        
        return answer;
    }
}