[프로그래머스] 코딩테스트 연습 > 2021 KAKAO BLIND RECRUITMENT > 메뉴 리뉴얼

조합 연습

import java.util.*;
class Solution {
    static HashMap<String, Integer> map = new HashMap<>();
    public ArrayList<String> solution(String[] orders, int[] course) {
        // String[] answer = {};
        ArrayList<String> answer = new ArrayList<>();
        for(int i=0;i<orders.length;i++){
            char[] c = orders[i].toCharArray();
            Arrays.sort(c);
            orders[i] = String.valueOf(c);
        }
        // orders에 사용된 모든 알파벳 조합 찾기 
        // 2 = ABCFG 에서 2 조합 = AB AC AF AG BC BF BG CF CG FG
        // 3 = ABCFG 에서 3 조합 = ABC ABF ABG BCF BCG CFG
        // 4 = ABCFG 에서 4 조합 = ABCF ABCG ABFG BCFG
        
        // 2 = AC 에서 2조합 = AC
            
        // 모두 찾아서 2번 이상 사용된 조합 출력
        
        for(int i=0;i<course.length;i++){
            for(int j=0;j<orders.length;j++){
                 comb(0, 0, orders[j], course[i], "");   
            }
        }
         
        for(int i=0;i<course.length;i++){
            int max = 0;
            for (Map.Entry<String, Integer> entry : map.entrySet()) {
                if (entry.getValue() >= 2 && entry.getKey().length() == course[i]) {
                    // 길이가 course[i] 인 것 중 최댓값
                        max = Math.max(max, entry.getValue());     
                    System.out.println(entry.getKey() + " " + entry.getValue());
                }
            }
             System.out.println(max);
             for (Map.Entry<String, Integer> entry : map.entrySet()) {
                if (entry.getValue() >= 2 && entry.getKey().length() == course[i] && entry.getValue() == max) {
                    answer.add(entry.getKey());                  
                }
            }
            
        }
        
        Collections.sort(answer);
        
        
        return answer;
    }
    
    static void comb(int count, int start, String order, int target, String s){
        if(count == target){
            map.put(s, map.getOrDefault(s, 0) + 1);
            return;
        }
        
        for(int i=start;i<order.length();i++){
            comb(count+1, i+1, order, target, s + order.charAt(i));    
        }
    }
}

 

검색해보니, Collections.max 로 리스트 내 max 값 바로 구할 수 있더라!

 

개선된 코드

import java.util.*;
class Solution {
    static HashMap<String, Integer> map = new HashMap<>();
    public ArrayList<String> solution(String[] orders, int[] course) {
        // String[] answer = {};
        ArrayList<String> answer = new ArrayList<>();
        for(int i=0;i<orders.length;i++){
            char[] c = orders[i].toCharArray();
            Arrays.sort(c);
            orders[i] = String.valueOf(c);
        }
        // orders에 사용된 모든 알파벳 조합 찾기 
        // 2 = ABCFG 에서 2 조합 = AB AC AF AG BC BF BG CF CG FG
        // 3 = ABCFG 에서 3 조합 = ABC ABF ABG BCF BCG CFG
        // 4 = ABCFG 에서 4 조합 = ABCF ABCG ABFG BCFG
        
        // 2 = AC 에서 2조합 = AC
            
        // 모두 찾아서 2번 이상 사용된 조합 출력
        for(int i=0;i<course.length;i++){
            map = new HashMap<>();
            for(int j=0;j<orders.length;j++){
                comb(0, 0, orders[j], course[i], "");
            }
            if(!map.isEmpty()){
                ArrayList<Integer> cntList = new ArrayList<>(map.values());
                int max = Collections.max(cntList);
                if(max >= 2) {
                    for(String s: map.keySet()){
                        if(map.get(s) == max) answer.add(s);
                    }
                }
            }
            
        }
         
        Collections.sort(answer);
        
        
        return answer;
    }
    
    static void comb(int count, int start, String order, int target, String s){
        if(count == target){
            map.put(s, map.getOrDefault(s, 0) + 1);
            return;
        }
        
        for(int i=start;i<order.length();i++){
            comb(count+1, i+1, order, target, s + order.charAt(i));    
        }
    }
}