2021 KAKAO BLIND RECRUITMENT : 메뉴 리뉴얼

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

코딩테스트 연습 - 메뉴 리뉴얼

 

// 코드

import java.util.*;
class Solution {
    
    List<Map<String, Integer>> FoodMaps = new ArrayList<>(); 
    int[] MaxCnt = new int[11];
    
    void comb(char[] str, int pos, StringBuilder candi) {
        
        if(pos >= str.length) {
            // 메뉴의 개수
            int len = candi.length();
            // 메뉴의 개수가 2개 이상일 때만 의미가 있다.
            if(len >= 2) {
                int cnt = FoodMaps.get(len).getOrDefault(candi.toString(), 0) + 1;
                FoodMaps.get(len).put(candi.toString(), cnt);
                MaxCnt[len] = Math.max(MaxCnt[len], cnt);
            }
            return; 
        }
        
        // 선택하고
        comb(str, pos+1, candi.append(str[pos]));
        // 선택 안하고
        candi.setLength(candi.length() - 1);
        comb(str, pos+1, candi);
        
    }
    
    public String[] solution(String[] orders, int[] course) {
        
        for(int i=0; i<=10; i++) FoodMaps.add(new HashMap<String, Integer>());
        
        // 모든 조합을 만든다.
        for(String str : orders) {
            char[] arr = str.toCharArray();
            Arrays.sort(arr);
            comb(arr, 0, new StringBuilder());
        }
        
        List<String> list = new ArrayList<>();
        for(int len : course) {
            for(Map.Entry<String, Integer> entry : FoodMaps.get(len).entrySet()) {
                // 주문횟수가 2이상이면서 MaxCnt랑 같은 경우
                if(entry.getValue() >= 2 && entry.getValue() == MaxCnt[len]) {
                    list.add(entry.getKey()); // 메뉴구성
                } 
            }
        }
        Collections.sort(list);
        
        String[] answer = new String[list.size()];
        for(int i=0; i<list.size(); i++) {
            answer[i] = list.get(i);
        }
        return answer;
    }
}

 

// 복습

import java.util.*;
 
class Solution {
    
    // 메뉴 길이별 값을 쌍으로 관리한다.
    List<Map<String, Integer>> FoodMaps = new ArrayList<>();
    // 메뉴 길이별 값중 가장 큰 값을 관리한다.
    int[] MaxCnt = new int[11];
    
    // comb : 모든 문자열 조합을 만드는 메서드
    void comb(char[] str, int pos, StringBuilder candi) {
        
        // 기저조건 : 현재 문자열의 길이가 전체 주어진 문자열의 길이와 같을경우.
        if(pos >= str.length) {
            // 메뉴의 개수
            int len = candi.length();
            // 메뉴의 메뉴의 개수가 2개 이상일 때만 의미가 있다.
            if(len >= 2) {
                // 해당 idx(len)메뉴의 개수의 위치에서 메뉴가 없으면 0을 있으면 있는 숫자를 가져와서 + 1 해준다.
                int cnt = FoodMaps.get(len).getOrDefault(candi.toString(), 0) + 1;
                // 해당위치에 메뉴와 메뉴의 카운트를 담아준다.
                FoodMaps.get(len).put(candi.toString(), cnt);
                MaxCnt[len] = Math.max(MaxCnt[len], cnt);
            }
            return;
        }
        
        // 다음 문자열을 선택한다.
        comb(str, pos+1, candi.append(str[pos]));
        // 다음 문자열을 선택안한다.
        candi.setLength(candi.length() - 1);
        comb(str, pos+1, candi);
        
    }
    
    public String[] solution(String[] orders, int[] course) {
        
        // course 배열의 크기는 1 이상 10 이하 라고 주어졌으니 미리 공간을 만들어 둔다.
        for(int i=0; i<=10; i++) FoodMaps.add(new HashMap<String, Integer>());
        
        // 메뉴의 모든 조합을 만든다.
        for(String str : orders) {
            char[] arr = str.toCharArray();            
            Arrays.sort(arr);
            comb(arr, 0, new StringBuilder());
        }
        
        // 요청한 코스에 맞춰 메뉴를 찾는다.
        List<String> list = new ArrayList<>();
        for(int len : course) {
            for(Map.Entry<String, Integer> entry : FoodMaps.get(len).entrySet()) {
                // 주문횟수가 2이상이면서 MaxCnt랑 같은 메뉴들을 찾는다.
                if(entry.getValue() >= 2 && entry.getValue() == MaxCnt[len]) {
                    // 해당 메뉴구성을 담는다.
                    list.add(entry.getKey());
                }
            }
        }
        
        // 정렬해준다.
        Collections.sort(list);        
        
        // 답을 반환한다.
        String[] answer = new String[list.size()];
        for(int i=0; i<list.size(); i++) {
            answer[i] = list.get(i);
        }
        return answer;
    }
}

 

// 핵심 아이디어