[프로그래머스] 2021 카카오 블라인드 메뉴리뉴얼 [JAVA]

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

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

코스 개수에 해당하는 메뉴 셋트의 가능한 조합을 카운트해서 크거나 같은 순으로 리스트에 저장했다.

 

import java.io.*;
import java.util.*;
public class kakao_2021_메뉴리뉴얼 {
	
	public static HashMap<String,Integer> hm;
	public static String []order;
	public static int [] courses;
	
	public static void go(int ord,int idx, int needCnt, int curCnt,StringBuilder str){
		if(needCnt == curCnt){
			String temp = str.toString();
			if(hm.containsKey(temp)){
				hm.put(temp, hm.get(temp)+1);
			}else{
				hm.put(temp, 1);
			}
			return;
		}
		for(int i=idx;i<order[ord].length();i++){
			str.append(order[ord].charAt(i));
			go(ord,i+1,needCnt,curCnt+1,str);
			str.delete(str.length()-1, str.length());
		}
	}
	
	public static void make(int cnt){
		for(int i=0;i<order.length;i++){
			StringBuilder str = new StringBuilder();
			go(i,0,cnt,0,str);
		}
	}
	public static String [] solution(String []orders, int[] course){		
		for(int i=0;i<orders.length;i++){
			char [] sorted = orders[i].toCharArray();
			Arrays.sort(sorted);
			orders[i] = new String(sorted);
		}
		Arrays.sort(orders,new Comparator<String>(){
			@Override
			public int compare(String o1, String o2) {
				return o1.compareTo(o2);
			}
		});
		
		order = orders;
		courses = course;
		ArrayList<String> ans = new ArrayList<String>();
		for(int i=0;i<course.length;i++){
			int cnt = course[i];
			//cnt개로 구성된 조합 모두 hashMap으로 카운트
			hm = new HashMap<String,Integer>();
			make(cnt);
			int maxCnt = 0;
			ArrayList<String> tempAns = new ArrayList<String>();
			Iterator<String> keys = hm.keySet().iterator();
			while(keys.hasNext()){
				String key = keys.next();
				int c = hm.get(key);
				if(c <2 ) continue;
				if(maxCnt < c){
					tempAns.clear();
					tempAns.add(key);
					maxCnt = c;
				}
				else if(maxCnt==c){
					tempAns.add(key);
				}
			}
			ans.addAll(tempAns);
		}
		String [] realAns = new String[ans.size()];
		for(int i=0;i<ans.size();i++){
			realAns[i] = ans.get(i);
		}
		Arrays.sort(realAns,new Comparator<String>(){
			@Override
			public int compare(String o1, String o2) {
				return o1.compareTo(o2);
			}
			
		});
		return realAns;
	}