[プログラマー]2021 KAKAO BLIND RECRUITMENT-メニュー更新

私のアイデア

正解

Java Code

import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.Set;
import java.util.Arrays;

class Solution {
    
    static Map<String, Integer>[] map;
    
    public String[] solution(String[] orders, int[] course) {
        PriorityQueue<String> pq = new PriorityQueue<String>();
		
		int people = orders.length;
        for(int i=0; i<people; i++) {
			char[] stringToChar = orders[i].toCharArray();
			Arrays.sort(stringToChar);
			orders[i] = new String(stringToChar);
		}
        
		map = new HashMap[21];
		
		for(int i=2; i<21; i++) {
			map[i] = new HashMap<>();
		}
		
		for(int i=0; i<people; i++) {
			int menuCnt = orders[i].length();
			boolean[] check = new boolean[menuCnt];
			SubSet(orders[i], 0, 0, menuCnt, check);
		}
		
		for(int i : course) {
            if(map[i].isEmpty()) continue;
            
			Set<String> keys = map[i].keySet();
			int max = 0;
			for(String s : keys) {
				if(map[i].get(s) > max) {
					max = map[i].get(s);
				}
			}
			
			if(max < 2) continue;
			
			for(String s : keys) {
				if(map[i].get(s) == max) {
					pq.offer(s);
				}
			}
		}
		
		int size = pq.size();
		String[] answer = new String[size];
		for(int i=0; i<size; i++) {
			answer[i] = pq.poll();
		}
		
		return answer;
    }
    
    private static void SubSet(String menu, int start, int cnt, int menuCnt, boolean[] check) {
		if(start == menuCnt) {
			if (cnt < 2) return;
			
			StringBuilder sb = new StringBuilder();
			for(int i=0; i<menuCnt; i++) {
				if(check[i]) {
					sb.append(menu.charAt(i));					
				}
			}
			
			String combMenu = sb.toString();
			if(map[cnt].containsKey(combMenu)) {
				map[cnt].replace(combMenu, map[cnt].get(combMenu)+1);
			}else {
				map[cnt].put(combMenu, 1);
			}
			return;
		}
		
		check[start] = true;
		SubSet(menu, start+1, cnt+1, menuCnt,check);
		check[start] = false;
		SubSet(menu, start+1, cnt, menuCnt,check);

	}
}