2021 KAKAO BLIND RECRUITMENT - 메뉴 리뉴얼

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

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

---

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.List;
import java.util.Map.Entry;

public class Solution {

	static HashMap<String, Integer> hm = new HashMap();
	
	public static String[] solution(String[] orders, int[] course) {
        
        for(String st : orders) {
        	
        	char[] arr = st.toCharArray();
        	Arrays.sort(arr);
        	
        	st = String.valueOf(arr);
        	
        	for(int i : course) {
        		/* 
        		 * 1. orders 에 들어있는 주문한 단품메뉴에서 
        		 * course 에 들어있는 코스요리를 구성하는 단품 메뉴 개수 만큼 모든 조합을 구한다.
        		*/
        		comb("", st, 0, 0, i);
        	}
        }
        
//        System.out.println(hm.toString());
        
        // 3. 최소 2명 이상의 손님으로 부터 주문된 단품 메뉴 조합에서만 취급하기 때문에 HashMap Value가 1인것은 제거.
        List<String> list = new ArrayList(hm.keySet());
        for(String s : list) if(hm.get(s) == 1) hm.remove(s);

        
        // 4. Key 길이 오름차순 + Value 내림차순 정렬
        List<Entry<String, Integer>> sortList = new ArrayList(hm.entrySet());
        
        Collections.sort(sortList, new Comparator<Entry<String, Integer>>() {
			@Override
			public int compare(Entry<String, Integer> o1, Entry<String, Integer> o2) {
				if(o1.getKey().length() != o2.getKey().length()) {
					return o1.getKey().length()-o2.getKey().length();
				} else {
					return o2.getValue().compareTo(o1.getValue());
				}
			}
        });
        
//        for(Entry<String, Integer> e : sortList) {
//        	System.out.println(e.getKey() + " " + e.getValue());	
//        }
        
        int keyLen = sortList.get(0).getKey().length();
        int maxValue = sortList.get(0).getValue();
        
        // 5. Value가 제일 큰것들만 남기고 나머지는 삭제
        for(int i=0; i<sortList.size(); i++) {
        	Entry<String, Integer> e = sortList.get(i);
        	String key = e.getKey();
        	int value = e.getValue();
        	
        	// key 길이가 같은데, value가 작으면 삭제 
        	if(keyLen == key.length() && maxValue > value) {
        		sortList.remove(i);
        		i--;
        	}
        	// key의 길이가 달라지면 값 교체
        	else if(keyLen != key.length()) {
        		keyLen = key.length();
        		maxValue = value;
        	}
        }
        
        // 6. key 기준 오름차순 정렬
        Collections.sort(sortList, new Comparator<Entry<String, Integer>>() {

			@Override
			public int compare(Entry<String, Integer> o1, Entry<String, Integer> o2) {
				return o1.getKey().compareTo(o2.getKey());
			}
			
        });
        
        String[] answer = new String[sortList.size()];
        
        for(int i=0; i<sortList.size(); i++) {
        	Entry<String, Integer> e = sortList.get(i);
        	answer[i] = e.getKey();
//        	System.out.println(e.getKey() + " " + e.getValue());
        }
        
        return answer;
    }
	
	public static void comb(String temp, String str, int start, int depth, int select) {
		if(depth == select) {
//			 System.out.println(temp);
			
			// 2. 조합의 갯수가 뽑혔으면, HashMap 에 조합을 담는다. Key = 코스메뉴 / Value = 갯수
			if(hm.containsKey(temp)) hm.put(temp, hm.get(temp) + 1);
			else hm.put(temp, 1);
			
			return;
		}
		
		for(int i = start; i < str.length(); i++) {
			temp += str.charAt(i);
			comb(temp, str, i+1, depth+1, select);
			temp = temp.substring(0, depth);
		}
	}
}