[2021 KAKAO BLIND RECRUITMENT] 메뉴 리뉴얼

2021 KAKAO BLIND RECRUITMENT 메뉴 리뉴얼

유형

• 조합
• Map

Map과 같은 자료구조에 대한 이해가 있어야 풀 수 있는 문제다. 다른 분들의 문제 풀이를 보니, 우선순위큐(Priority Queue)를 활용한 경우도 있었다.

문제 풀이에 대한 감을 잡기 위해, 카카오 공식 문제 해설을 먼저 참고하였다.

문제 풀이

먼저 문제에 대한 해답을 얻기 전에, 각 메뉴별로 가능한 모든 조합을 만들어 봅니다. 예를 들어 “ABCD”의 경우 다음과 같이 11가지 조합이 가능합니다.

“AB”, “AC”, “AD”, “BC”, “BD”, “CD”, “ABC”, “ABD”, “ACD”, “BCD”, “ABCD”
위와 같이 각 메뉴에서 가능한 모든 조합을 만들었다면, 각 조합의 개수를 세면 됩니다. 이때 “ABC”와 “CBA”를 같은 조합으로 세는 점을 주의해야 합니다. 쉽게 해결하는 방법으로는 처음에 각 문자열을 알파벳 순서로 정렬하거나, 만들어진 조합 문자열을 정렬하는 방법이 있겠습니다.

각 조합별로 개수를 셌다면, 최종적으로 문자열의 길이가 같은 조합 중 가장 많이 나타난 조합은 무엇인지 찾으면 됩니다.

코드

import java.util.*;

class Solution {
    static TreeMap<String, Integer> courseCandidate;

    public String[] solution(String[] orders, int[] course) {
        // 주문받은 메뉴들로 가능한 모든 조합을 만들어 본다.
        // 각 메뉴에서 가능한 모든 조합을 만들었다면, 각 조합의 개수를 세면 된다.
        Set<String> menus = new TreeSet<>();
        courseCandidate = new TreeMap<>();  //TreeSet, TreeMap은 요소를 오름차순으로 저장
        Set<String> finalCourse = new TreeSet<>();

        for (String order : orders) {
            String[] orderedMenus = order.split("");
            Arrays.sort(orderedMenus);
            // nCr에서 n은 메뉴의 개수, r은 course 배열의 값들
            int menuCount = orderedMenus.length;
            Arrays.stream(course)
            .forEach(r -> combination(orderedMenus, new boolean[menuCount], 0, menuCount, r));
        }

        // 각 조합별로 개수를 셌다면, 최종적으로 문자열의 길이가 같은 조합 중 가장 많이 나타난 조합은 무엇인지 찾는다.
        // 2명 이상 주문하지 않았다면 제거한다.
        Arrays.stream(course).forEach(
                r -> {
                    courseCandidate.entrySet().stream()
                            .filter(e -> e.getKey().length() == r)
                            .max(Map.Entry.comparingByValue())
                            .ifPresent(e -> {
                                int max = e.getValue();
                                if(max != 1) {
                                    courseCandidate.entrySet().stream()
                                            .filter(en -> en.getKey().length() == r)
                                            .filter(en -> en.getValue() == max)
                                            .forEach(en -> finalCourse.add(en.getKey()));
                                }
                            });
                }
        );

        String[] answer = finalCourse.toArray(new String[0]);
        return answer;
    }

    static void combination(String[] arr, boolean[] visited, int start, int n, int r) {
        if (r == 0) {
            String candidate = makeComb(arr, visited, n);
            if(courseCandidate.containsKey(candidate)) {
                courseCandidate.put(candidate, courseCandidate.get(candidate) + 1);
            } else {
                courseCandidate.put(candidate, 1);
            }
            return;
        }

        for (int i = start; i < n; i++) {
            visited[i] = true;
            combination(arr, visited, i + 1, n, r - 1);
            visited[i] = false;
        }
    }

    static String makeComb(String[] arr, boolean[] visited, int n) {
        String comb = "";
        for (int i = 0; i < n; i++) {
            if (visited[i]) {
                comb += arr[i];
            }
        }
        return comb;
    }
}