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

프로그래머스

 

💬 문제 설명

손님들이 주문한 메뉴들을 기반으로 코스요리를 구성하는데 손님들이 가장 많이 주문한 메뉴들로 코스 요리를 구성하고 메뉴 이름의 알파벳 순으로 배열을 구성해서 반환하라.

 

📌 주의 사항

• 순열로 구하면 시간 초과... → 어차피 정렬된 순서의 메뉴를 선택해야 하므로 메뉴 목록을 미리 정렬해서 조합의 경우의 수로 구하자!
• 가장 많이 주문한 코스요리 메뉴의 개수가 여러 개인 경우 모든 조합 반환

 

👌 문제 풀이

1. orders 배열의 값(메뉴 목록)들을 알파벳 순으로 정렬
   • String을 char[] 배열로 변환하여 Arrays.sort 활용
2. course 배열의 값(메뉴 개수)만큼 조합의 경우의 수로 메뉴를 뽑아서 코스요리를 구성하고 해당 코스요리를 카운팅해서 저장
   • `public Map<String, Integer> counts = new HashMap<>();`
3. 가장 개수가 많은 코스요리 조합을 구해서 리스트에 저장
4. 코스요리 조합의 리스트를 알파벳 순으로 정렬
5. 리스트를 배열로 변환

 

💻 코드

import java.util.Map;
import java.util.HashMap;
import java.util.List;
import java.util.ArrayList;
import java.util.Arrays;

class Solution {
    
    public List<Character> menus = new ArrayList<>();
    public Map<String, Integer> counts = new HashMap<>();
    public int[] selected;
    
    public String[] solution(String[] orders, int[] course) {
        // 1. orders 배열 정렬
        List<String> sortedOrders = new ArrayList<>();
        for (String order: orders) {
            char[] temp = order.toCharArray();
            Arrays.sort(temp);
            sortedOrders.add(new String(temp));
        }
        
        // 2. 주어진 개수의 조합으로 코스요리 구성
        for (String order : sortedOrders) {
            for (int r : course) {
                selected = new int[r];
                comb(0, 0, r, order);
            }
        }
        
        // 3. 가장 개수가 많은 코스요리 구성 찾기
        List<String> keySet = new ArrayList<>(counts.keySet());
        List<String> answerList = new ArrayList<>();
        
        // 사이즈 별로 선택
        for (int size : course) {
            // 코스요리의 최대 개수 구하기
            int maxCnt = 2; // 최소 2명 이상의 손님에게서 주문된 구성만 코스요리 후보에 들어감
            
            for (String key : keySet) {
                if (key.length() == size && counts.get(key) >= maxCnt) {
                    maxCnt = counts.get(key);
                }
            }
            
            // 최대 개수를 가지는 코스요리 구하기
            for (String key : keySet) {
                int cnt = counts.get(key);

                if (key.length() == size && cnt == maxCnt) {
                    answerList.add(key);
                }
            }
        }
        
        // 4. List -> Array
        String[] answer = answerList.toArray(new String[0]);

        // 코스요리 이름 순으로 정렬
        Arrays.sort(answer);
        
        return answer;
    }
    
    public void comb(int r, int idx, int R, String order) {
        if (r == R) {
            String course = "";
            for (int i : selected) {
                course += order.charAt(i);
            }

            if (counts.get(course) == null) {
                counts.put(course, 0);
            }

            counts.put(course, counts.get(course) + 1);

            return;
        }
        
        for (int i = idx; i < order.length(); i++) {
            selected[r] = i;
            comb(r + 1, i + 1, R, order);
        }
    }
    
}

🎓 배운 것

1.