[프로그래머스/해시] Lv2. 메뉴 리뉴얼 (자바)

해시

1. 조합을 만들 땐 정렬을 고려하자

2. HashMap 의 기본 형태는 name : count

3. 재귀 - 탈출조건 + 수행 동작

 

import java.util.*;

// 1. 각 길이 별로 가능한 모든 조합 생성
// 2. 조합 별 개수를 저장하고, 가장 많은 조합만 저장 
class Solution {
    
    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++) {
            char[] arr = orders[i].toCharArray();
            Arrays.sort(arr);
            orders[i] = String.valueOf(arr);
        }
        
        // 2. 각 order 기준으로 courseLength 만큼의 조합 만들기
        for(int courseLength : course) {
            for(String order : orders) {
                combination("", 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;
    }
    
    // order 기준으로 courseLength 만큼의 조합 만들기
    // order : 현재까지 조합된 코스
    // others : 아직 사용되지 않은 메뉴
    // count : 코스 길이
    public void combination(String order, String others, int count) {
        // 탈출조건 : count 가 0 이 되었을 때
        if(count == 0) {
            hashMap.put(order, hashMap.getOrDefault(order, 0) + 1);
            return;
        }
        
        // 수행동작 : 0 부터 남은 메뉴들의 length 까지 조합한다.
        for(int i=0; i<others.length(); i++) {
            combination(order + others.charAt(i), others.substring(i+1), count-1);
        }
        
    }
}

 

출처: https://coding-grandpa.tistory.com/102 [개발자로 취직하기:티스토리]