22-12-19 코딩테스트 해쉬#4 (메뉴 리뉴얼)

해쉬를 활용한 메뉴 리뉴얼

+문제분석 >>> 정렬

1. 각 orvder 정렬
   각 길이별로 가능한 모든 조합을 생성한다.
2. 코스 길이별 조합 생성
   각 길이별로 가능한 모든 조합을 생성한다.
3. 가장 많은 조합 저장
   조합 별 개수를 저장하고, 가장 많은 조합만 answer에 저장한다.

import java.util.*;

class Solution07{
    List<String> answerList=new ArrayList<>();
    Map<String,Integer>hashMap = new HashMap<>();
    public String[] solution(String[]orders,int[] course){
        // 1. 각 order 정렬
        for(int i =0; i<orders.length;i++){
            // string 차체를 정렬이 불가능 char 변환
            char[] arr =orders[i].toCharArray();
            Arrays.sort(arr);
            orders[i]= String.valueOf(arr);

        }

        // 2. 각 order를 기준으로 coursdlength만큼 조합 만들기
        for(int courseLength : course){
            for(String order : orders){
            combinatrion("",order,courseLength);
            }
            // 3. 가장 많은 조합을 answer에 저장한다.
            // 리스트로 만든 이유는 최대값을 찾기 쉽기때문에
            if(hashMap.isEmpty()){
                List<Integer> countList = new ArrayList<>(hashMap.values());
                int max = Collections.max(countList);

                if(max>1){
                    for(String key : hashMap.keySet()){
                        if(hashMap.get(key)==max){
                            answerList.add(key);

                        hashMap.clear();
                        }
                    }
                }
            }

        }

        Collections.sort(answerList);
        String[] answer = new String[answerList.size()];
        for(int i=0; i<answer.length;i++){
            answer[i]= answerList.get(i);
        }
        return answer;
    }
                // 현제까지 조합 코스, 아직까지 사용 안한 알파벳, 몇개를 더 조합해야하는 카운터
    public void combinatrion(String order, String others, int count){
        // 탈출 조건
        if(count==0){
           hashMap.put(order, hashMap.getOrDefault(others, 0)+1); 
            return ;
        }
        // 수행 동작 : 0부터 length까지 조합
        for(int i=0;i<others.length();i++){
            combinatrion(order+others.charAt(i), others.substring(+1), count-1);
        }
    }

    public static void main(String[] args) {
        Solution07 sol = new Solution07();
        String[] orders={"ABCFG","AB","ACDE","ACDEH"};
        int[] course={2,3,4};
        System.out.println(sol.solution(orders,course));
    }
}