[Programmers] LV2 - 메뉴 리뉴얼

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

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

 

문제 파악

1. 손님이 주문한 단품 메뉴 조합을 분해하여 각 손님에 대한 단품 메뉴의 조합을 만든다.

예를 들면 1번 손님은 A,B,C,F,G를 시켰는데 이 정보를 가지고 만들 수 있는 조합은 (A, B), (A, C), (A, F), (A, G), (B, C)... 등등으로 나눌 수 있다.

2. 조합의 경우 순서와 상관이 없어야 하므로 문자를 우선순위 큐로 분해 하여 넣었다가 다시 재조립해준다.

3. 만들 수 있는 조합을 HashMap<String,Integer>의 객체에 put 해준다. 기존에 존재할 경우 +1

4. HashMap에 값을 넣어 줄 때 마다 해당 조합의 길이 (A, B) = 2, (A, B, C) = 3에서 Max 값을 구한다.

("스카피"는 이전에 각 손님들이 주문할 때 가장 많이 함께 주문한 단품메뉴들을 코스요리 메뉴로 구성하기로 했습니다.)

 

import java.util.*;
class Solution {
    
    static HashMap<String,Integer> hm = new HashMap<String,Integer>();
    static int[] menulen;
    public String[] solution(String[] orders, int[] course) {
        
        StringBuilder sb = new StringBuilder();
        
        ArrayList<String> list = new ArrayList<String>();
        menulen = new int[11];
        
        for(int idx = 0; idx<orders.length;idx++)
        {
            String order = ConvertString(orders[idx]);
            for(int idx2 = 0; idx2< course.length;idx2++)
            {
                int cr = course[idx2];
                MenuAll(order,cr,sb,0);                
            }
        }
           
        for(String key : hm.keySet())
        {
            int keylen = key.length();
            if(menulen[keylen] == hm.get(key) && hm.get(key) >=2)
            {
                    list.add(key);
            }
        }        
        
        Collections.sort(list);
        
        String[] answer = new String[list.size()];
        
        
        for(int sz = 0; sz<list.size();sz++){
            answer[sz] = list.get(sz);
        }
        
        return answer;
    }
    
    public void MenuAll(String order,int course,StringBuilder sb,int idx)
    {
        int len = sb.length();
        if(course == len){            
            String key = sb.toString();
            hm.put(key,hm.getOrDefault(key,0)+1);
            menulen[len] = Math.max(menulen[len],hm.get(key));
            return;
        }
        
        for(int i = idx;i<order.length();i++)
        {
            sb.append(order.charAt(i));
            MenuAll(order,course,sb,i+1);
            sb.setLength(sb.length() - 1);
        }
    }
        
    public String ConvertString(String str)
    {
      StringBuilder sb2 = new StringBuilder();
        PriorityQueue<Character> pq = new PriorityQueue<Character>();
        
        for(int idx = 0; idx<str.length();idx++)
        {
            pq.add(str.charAt(idx));
        }
        
        while(!pq.isEmpty()){
            sb2.append(pq.poll());
        }
        
        return sb2.toString();
        
    }
}