2021 카카오 신입 메뉴 리뉴얼 level2 - java

 

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

해당 문제의 제한 크기가 크지 않은 걸 알 수 있다.

이러면 생각해볼 수 있는게 재귀가 있다.

dfs를 통해 course 길이 별 order의 경우의 수를 모두 구해줬다.

dfs가 종료된 후, order의 경우의 수 중에서 course 길이 별 최대로 주문된 코스요리(정답)를 구해줬다.

import java.util.*;

class Solution {
    Set<String> set = new HashSet<>();
    Map<String, Integer> setMenu = new HashMap<>();
    int max = 2;

    public String[] solution(String[] orders, int[] course) {
        String[] answer = {};
        List<String> list = new ArrayList<>();
        for (int c = 0; c < course.length; c++) {
            int courseLength = course[c];
            for (int i = 0; i < orders.length; i++) {
                String order = orders[i];
                if (order.length() < courseLength) continue;
                char[] charArray = order.toCharArray();
                Arrays.sort(charArray);
                order = String.valueOf(charArray);
                for (int orderIndex = 0; orderIndex < order.length(); orderIndex++) {
                    char[] menuList = new char[courseLength];
                    menuList[0] = order.charAt(orderIndex);
                    BackTracking(menuList, order, 1, orderIndex + 1);
                }
            } // courseLength 별 setMenu 조사 완료

            for (Map.Entry<String, Integer> entry : setMenu.entrySet()) {
                if (max == entry.getValue()) {
                    list.add(entry.getKey());
                    System.out.println(entry.getKey());
                }
            }
            max = 2;
            set = new HashSet<>();
            setMenu = new HashMap<>();
        }

        Collections.sort(list);
        answer = new String[list.size()];
        int i = 0;
        for (String s : list) {
            answer[i++] = s;
        }
        return answer;
    }

    private void BackTracking(char[] menuList, String order, int index, int startIndex) {
        if (index == menuList.length) {
            // 이미 있으면 set.add가 False 리턴함
            String newMenu = String.valueOf(menuList);
            if (newMenu.length() == menuList.length) {
                setMenu.put(newMenu, setMenu.getOrDefault(newMenu, 0) + 1);
                if (max < setMenu.get(newMenu)) {
                    max = setMenu.get(newMenu);
                }
            }
            return;
        }
        for (int i = startIndex; i < order.length(); i++) {
            menuList[index] = order.charAt(i);
            BackTracking(menuList, order, index + 1, i + 1);
        }

    }
}

public class code {
    public static void main(String[] args) {
        Solution s = new Solution();
        String[] orders = {"XYZ", "XWY", "WXA"};
        int[] course = {2, 3, 4};
        String[] answer = s.solution(orders, course);
        for (String str : answer) {
            System.out.println(str);
        }
    }
}