[2021 KAKAO BLIND RECRUITMENT] 메뉴 리뉴얼

문제 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/72411#

이 문제는 조합과 우선 순위 큐를 사용하여 풀 수 있습니다. 문제에서 요구하는 메뉴들은 orders의 문자열 중 course 개수만큼 선택하는 조합과 같습니다. 따라서 조합 알고리즘을 이용하여 선택 후 HashMap에 저장하여 개수를 카운트하여 가장 많은 수의 메뉴를 저장합니다.

여기서 주의해야 할 점은 배열 및 배열의 각 원소들이 모두 오름차순 정렬되어야 한다는 점입니다. 이를 위해 조합으로 선택하기 전 문자열을 오름차순으로 정렬하는 과정을 겪어야 합니다. 우선 순위 큐를 이용하여 한 글자씩 추가한 후 순서대로 StringBuilder에 추가하면 됩니다.

다음은 코드입니다.

import java.util.*;

class Solution {
    static HashMap<String,Integer> map;
    static boolean[] check;
    static int max;
    static Queue<String> queue;
    static PriorityQueue<String> pq = new PriorityQueue<>();
    
    public String[] solution(String[] orders, int[] course) {
        for(int i=0;i<course.length;i++){
            map = new HashMap<>();
            check = new boolean[20];
            queue = new LinkedList<>();
            max = 0;
            int R = course[i];
            
            for(int j=0;j<orders.length;j++){
                int N = orders[j].length();
                
                PriorityQueue<Character> pq = new PriorityQueue<>();
                for(int k=0;k<orders[j].length();k++){
                    pq.add(orders[j].charAt(k));
                }
                StringBuilder sb = new StringBuilder();
                while(!pq.isEmpty()){
                    sb.append(pq.poll());
                }
                
                combination(N,R,0,0,sb.toString(),new StringBuilder());
            }
            
            ArrayList<String> menu = new ArrayList<>(map.keySet());
            for(int j=0;j<menu.size();j++){
                if(max+1 == map.get(menu.get(j)))
                    pq.add(menu.get(j));
            }
        }
        
        String[] answer = new String[pq.size()];
        int idx = 0;
        while(!pq.isEmpty()){
            answer[idx] = pq.poll();
            idx++;
        }
        
        return answer;
    }
    
    
    static void combination(int N, int R, int cnt, int start, String req, StringBuilder res){
        if(cnt==R){
            int num = 1;
            if(map.containsKey(res.toString())){
                num = map.get(res.toString());
                map.replace(res.toString(),num+1);
            }
            else map.put(res.toString(),num);
            
            max = Math.max(max,num);
            return;
        }

        for(int i=start;i<N;i++){
            if(!check[i]){
                check[i] = true;
                res.append(req.charAt(i));
                combination(N,R,cnt+1,i+1,req,res);
                check[i] = false;
                res.deleteCharAt(res.length() - 1);
            }
        }
    }
}