[프로그래머스] 메뉴 리뉴얼 - 2021 KAKAO BLIND RECRUITMENT

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

프로그래머스

 

LEVEL 2, 풀이법 : 순/조/부 + HashMap , 풀이 시간 1h

 

<step 1> 메뉴를 모두 오름차순으로 될 수 있도록 정렬한다.

//1. orders 메뉴 정렬
for(int i = 0; i < orders.length; i++){
    char[] arr = orders[i].toCharArray();
    Arrays.sort(arr);
    orders[i] = String.valueOf(arr);
}

 

<step 2> Combination으로 길이 별 모든 경우의 수를 확인한다.

public void Combi(String order, String others, int depth){
    if(order.length() == depth){
        hashMap.put(order, hashMap.getOrDefault(order, 0) + 1);
        return;
    }

    for(int i = 0; i < others.length(); i++){
        Combi(order + others.charAt(i), others.substring(i+1), depth);
    }
}

 

<step 3> course 에 맞는 길이와 모든 경우의 수를 확인한다

    // 2. course에 맞게 조합 뽑기.
    for(int c : course){
        for(String o : orders){
            Combi("", o, c);
        }

        // 3. 길이 별로 max값 뽑기
        if(!hashMap.isEmpty()){
            List<Integer> countList = new ArrayList<>(hashMap.values());
            int m_value = Collections.max(countList);

            if(m_value > 1){
                for(String k : hashMap.keySet()){
                    if(hashMap.get(k) == m_value){
                        answerList.add(k);
                    }
                }
            }
            hashMap.clear();
        }
    }

 

<전체 코드>

import java.util.*;

class Solution {
    
    static ArrayList<String> answerList = new ArrayList<>();
    static Map<String, Integer> hashMap = new HashMap<>();
    
    public String[] solution(String[] orders, int[] course) {
        
        //1. orders 메뉴 정렬
        for(int i = 0; i < orders.length; i++){
            char[] arr = orders[i].toCharArray();
            Arrays.sort(arr);
            orders[i] = String.valueOf(arr);
        }
        
        // 2. course에 맞게 조합 뽑기.
        for(int c : course){
            for(String o : orders){
                Combi("", o, c);
            }
            
            // 3. 길이 별로 max값 뽑기
            if(!hashMap.isEmpty()){
                List<Integer> countList = new ArrayList<>(hashMap.values());
                int m_value = Collections.max(countList);
                
                if(m_value > 1){
                    for(String k : hashMap.keySet()){
                        if(hashMap.get(k) == m_value){
                            answerList.add(k);
                        }
                    }
                }
                hashMap.clear();
            }
        }
        
        Collections.sort(answerList);
        String[] answer = new String[answerList.size()];
        for(int i = 0; i < answerList.size(); i++){
            answer[i] = answerList.get(i);
        }
        
        return answer;
    }
    
    public void Combi(String order, String others, int depth){
        if(order.length() == depth){
            hashMap.put(order, hashMap.getOrDefault(order, 0) + 1);
            return;
        }
        
        for(int i = 0; i < others.length(); i++){
            Combi(order + others.charAt(i), others.substring(i+1), depth);
        }
    }
}