2021 KAKAO BLIND RECRUITMENT
https://programmers.co.kr/learn/courses/30/lessons/72411

카카오 코테에 니니즈 등장하면 너무 심장 몽글몽글해져서 문제풀이 불가

🥚문제

🥚입력/출력

🧂아이디어

• makeMenu(String[] orders)
  • orders에 등장하는 메뉴들(알파벳들)을 저장하는 ArrayList를 return

• combination(ArrayList<Character> menu, int combi_number)
  • combi_number 개수로 이루어진 조합을 저장한 ArrayLIst를 return
  • 입력값이 ["XYZ", "XWY", "WXA"], [2, 3, 4]일 때,
  • 2개의 메뉴로 이루어진 조합
    [XY, XZ, XW, XA, YZ, YW, YA, ZW, ZA, WA]
    3개의 메뉴로 이루어진 조합
    [XYZ, XYW, XYA, XZW, XZA, XWA, YZW, YZA, YWA, ZWA]
    4개의 메뉴로 이루어진 조합
    [XYZW, XYZA, XYWA, XZWA, YZWA]
    와 같은 결과를 얻어냄
  • 내부에서 makeCombination 메소드가 중복 없이, 순서 관계 없이, 정해진 개수를 선택하는 조합을 재귀적으로 만들어내고 있음

• countForCombination(ArrayList<String> combinations, String[] orders)
  • combination 메소드를 통해 만들어진 조합들이 손님들의 주문에서 등장하는 횟수를 카운트한 뒤, 그 정보를 담은 int[ ]를 리턴
  • 위 combination메소드의 설명과 입력값이 같다고 할 때
  • 2개의 메뉴로 이루어진 조합
    2, 1, 2, 1, 1, 1, 0, 0, 0, 1
    3개의 메뉴로 이루어진 조합
    1, 1, 0, 0, 0, 1, 0, 0, 0, 0
    4개의 메뉴로 이루어진 조합
    0, 0, 0, 0, 0
    과 같은 결과를 얻어냄

• findMaxIndex(int[] count_combinations)
  • countForCombination을 통해 조합들이 등장하는 횟수를 카운트한 정보를 얻었으면, 그 중 가장 빈번하게 등장하는 조합들의 combination에서의 index를 찾는다. (최빈 조합을 찾아낸다)
  • 이때, 문제의 조건에서 최소 2명 이상의 손님으로부터 주문된 단품메뉴 조합에 대해서만 코스요리 메뉴 후보에 포함한다고 했으므로 가장 빈번하게 등장하는 조합의 등장 횟수가 1 이하라면 max_index는 빈 배열을 리턴받는다.

• findCourseMenu(combinations, max_index)
  • max_index를 활용해서 조합을 찾아낸다
  • combination메소드의 설명과 입력값이 같다고 할 때
  • 2개의 메뉴로 이루어진 조합
    XY, XW
    3개의 메뉴로 이루어진 조합
    없음
    4개의 메뉴로 이루어진 조합
    없음

• 마지막으로, answer array를 구성할 때, 각각의 요소도 오름차순으로 정렬되어 있고, String array 전체도 오름차순으로 정렬하여 return함에 주의한다.

🍳코드

import java.util.ArrayList;
import java.util.Arrays;

class Solution {
    public String[] solution(String[] orders, int[] course) {
        
        // 임시로 결과를 담을 arraylist
        ArrayList<String> temp = new ArrayList<>();
        
        // orders에서 등장한 메뉴명을 arraylist에 저장
        ArrayList<Character> menu = makeMenu(orders);
        
        for(int i = 0; i < course.length; i++){
            // course[i]개로 구성된 조합 구하기
            // 예시
            // [AB, AC, AF, AG, AD, AE, AH, BC, BF, BG, BD, BE, BH, CF, CG, CD, CE, CH, FG, FD, FE, FH, GD, GE, GH, DE, DH, EH]
            ArrayList<String> combinations = combination(menu, course[i]);
            
            // 조합들이 등장하는 횟수 count
            // 에시
            // [1, 4, 1, 1, 2, 2, 1, 2, 2, 2, 0, 0, 0, 2, 2, 3, 3, 1, 2, 0, 0, 0, 0, 0, 0, 3, 1, 1]
            int[] count_combinations = countForCombination(combinations, orders);
            
            // count_combinations의 max값 구하고, max값이 등장하는 idx 구하기
            int[] max_index = findMaxIndex(count_combinations);
            
            // combinations에서, max_index의 요소 값을 인덱스로 가지는 요소 -> 가능한 코스요리 조합
            String[] courseMenu = findCourseMenu(combinations, max_index);
            
            // temp에 추가
            for(String courseMenuItem : courseMenu){
                temp.add(courseMenuItem);
            }
        }
        
        // answer array 구성
        String[] answer = new String[temp.size()];
        for(int i = 0; i < temp.size(); i++){
            answer[i] = sortString(temp.get(i));
        }
        // ansewer array sort
        Arrays.sort(answer);
        // return
        return answer;
    }
    
    // sortString
    private String sortString(String str){
        char[] chars = str.toCharArray();
        Arrays.sort(chars);
        String result = new String(chars);
        return result;
    }
    
    // findCourseMenu
    private String[] findCourseMenu(ArrayList<String> combinations, int[] max_index){
        String[] result = new String[max_index.length];
        for(int i = 0; i < max_index.length; i++){
            result[i] = combinations.get(max_index[i]);
        }
        return result;
    }
    
    // findMaxIndex
    private int[] findMaxIndex(int[] count_combinations){
        ArrayList<Integer> max_index = new ArrayList<>();
        int max_value = findMax(count_combinations);
        // max_value가 1 이하라면 빈 배열을 리턴함
        if(max_value <= 1){
            int[] empty = {};
            return empty;
        }
        for(int i = 0; i < count_combinations.length; i++){
            if(count_combinations[i] == max_value)
                max_index.add(i);
        }
        int[] result = new int[max_index.size()];
        for(int i = 0; i < max_index.size(); i++){
            result[i] = max_index.get(i);
        }
        return result;
        
    }
    
    // findMax
    private int findMax(int[] count_combinations){
        int max_value = 0;
        for(int count : count_combinations){
            max_value = count > max_value? count : max_value;
        }
        return max_value;
    }
    
    // countForCombination
    private int[] countForCombination(ArrayList<String> combinations, String[] orders){
        int[] count_combinations = new int[combinations.size()];
        int count_idx = 0;
        for(String combi : combinations){
            // 조합을 손님이 주문한 횟수를 count
            int count = 0;
            for(String order : orders){
            // 손님의 order에 combi 조합이 포함되어 있는지 확인한다
                boolean ok = true;
                for(int idx = 0; idx < combi.length(); idx++){
                    String ch = combi.substring(idx, idx + 1);
                    if(!order.contains(ch)){
                        ok = false;
                        break;
                    }
                }
                // 포함되어 있을 시 count++
                if (ok)
                    count++;
            }
            // 조합을 주문한 횟수인 count를 저장한다
            count_combinations[count_idx++] = count;
        }
        return count_combinations;
    }
    
    // makeMenu
    private ArrayList<Character> makeMenu(String[] orders){
        ArrayList<Character> menu = new ArrayList<>();
        for(String order : orders){
            for(int i = 0; i < order.length(); i ++){
                Character x = order.charAt(i);
                if(!menu.contains(x))
                    menu.add(x);
            }
        }
        return menu;
    }
    
    // combination
    private ArrayList<String> combination(ArrayList<Character> menu, int combi_number){
        int numerator = 1;
        for(int i = menu.size(); i >= menu.size() - combi_number; i--){
            numerator *= i;
        }
        int denominator = factorial(combi_number);
        int count = (int)(numerator / denominator);
        
        boolean[] menu_visited = new boolean[menu.size()];
        for(int i = 0; i < menu.size(); i++){
            menu_visited[i] = false;
        }
        ArrayList<String> result = makeCombination(menu, combi_number, "", menu_visited, new ArrayList<String>());
        return result;
    }

    // makeCombination
    private ArrayList<String> makeCombination(ArrayList<Character> menu, int combi_number, String combi, boolean[] menu_visited, ArrayList<String> result){

        if(combi_number == 0){
            result.add(combi);
            return result;
        }

        for(int i = 0; i < menu.size(); i++){
            if(combi.indexOf(menu.get(i)) == -1 && !menu_visited[i]){ // combi String 내에 존재하지 않는 문자이고, 방문한 적이 없으면 추가한다
                boolean[] new_menu_visited = new boolean[menu_visited.length];
                for(int j = 0; j < menu_visited.length; j++){
                    new_menu_visited[j] = menu_visited[j];
                }
                new_menu_visited[i] = true;
                makeCombination(menu, combi_number - 1, combi + menu.get(i), new_menu_visited, result);
            }
            menu_visited[i] = true;
        }
        return result;
    }
    
    // factorial
    private int factorial(int n){
        if(n == 1)
            return 1;
        return n * factorial(n-1);
    }
}

🍵추가

• 코드가 너무 길어졌는데, 실전에서 시행착오 없이 이렇게 긴 코드를 짤 수 있을지는 잘 모르겠다.🥺 훌쩍스...

• 어딘가 개선이 필요하다는 말인데, 다른 사람들의 풀이를 보다 멋진 아이디어를 찾아냈다!
  

• 문제의 조건인 '각 손님의 주문에 메뉴가 중복해서 등장하지 않음' 을 이용해서 각 손님의 주문별로 조합을 만든 것이 똑똑쓰

  • 나는 모든 손님이 주문한 메뉴를 먼저 구한 뒤, 그 메뉴들로 가능한 모든 조합을 구해내고 등장하지 않는 조합을 쳐내는 방식으로 했는데
  • 이런 나의 방법에 비해 의심의 여지 없이 효율적. 손님 한명한명의 메뉴 주문 정보로부터 가능한 조합들을 먼저 구하기 때문.

• HashMap, PriorityQueue등의 자료구조를 적절하게 이용한 것도 센스 있었다...

• ⭐ 위 코드를 보면서 HashMap의 getOrDefault라는 메소드를 알게 되었다

• ⭐ 어차피 오름차순으로 정렬할거라면, PriorityQueue에 담아두고 poll해서 결과를 구성하는 세련된 방법도 배웠다!

세련된 코드를 짤 수 있을 때까지 정진하자...ㅎ