[2021 KAKAO BLIND RECRUITMENT] 메뉴 리뉴얼

문제 설명

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

풀이

1. ABCFG 혹은 AC와 같은 주문 배열로부터 길이가 2, 3, 4인 조합 문자열을 뽑아냅니다.
   ex) AB, AC, AF, AG ...

2. 1.에서 뽑아낸 각 문자열에 대해 주문횟수를 저장한 맵을 만듭니다.

{ "AB": 1, "AC": 2, "AF": 3 ... }

3. 2.에서 뽑아낸 문자열 중 가장 큰 값을 가진 문자열을 모두 선택한 뒤 정렬하여 돌려줍니다.

대략적인 구현은 위와 같고, 가장 문제가 될만한 부분은 1.에서 조합 문자열을 뽑아내는 부분일것 같습니다.

가능한 모든 문자열 조합을 찾아내는 코드는 일반적인 DFS 알고리즘을 통해 구현할 수 있습니다.

public void main(String[] args) {
	List<String> result = new ArrayList<>();
    
    // abcde의 다섯 글자 중에서 길이가 2인 문자열을 뽑아낸다.
	findCombinations("abcde", 2, new StringBuilder(), 0, result);
}

private void findCombinations(String alphabet, int length,
    StringBuilder current, int index, List<String> result) {
    
    if (current.length() == length) {
        result.add(current.toString());
        return;
    }

    for (int i = index; i < alphabet.length(); i++) {
        current.append(alphabet.charAt(i));
        findCombinations(alphabet, length, current, i + 1, result);
        current.deleteCharAt(current.length() - 1);
    }
}

이제 전체 코드를 살펴보겠습니다.

public String[] solution(String[] orders, int[] course) {
    List<String> answer = new ArrayList<>();

    for (int numMenus : course) {
        List<String> combinations = new ArrayList<>();
        for (String order : orders) {
            findCombinations(
                order, numMenus, new StringBuilder(), 0, combinations);
        }

        Map<String, Integer> numOrdersByMenu =
            getNumOrdersByMenu(orders, combinations);

        // 최소 2명 이상이 주문한 메뉴만 코스 요리에 포함
        int maxNumOrders = 2;
        for (String key : numOrdersByMenu.keySet()) {
            int numOrder = numOrdersByMenu.get(key);
            if (numOrder >= maxNumOrders) {
                maxNumOrders = numOrder;
            }
        }

        for (String key : numOrdersByMenu.keySet()) {
            if (numOrdersByMenu.get(key) == maxNumOrders) {
                answer.add(key);
            }
        }
    }

    String[] ret = new String[answer.size()];
    for (int i = 0; i < answer.size(); i++) {
        ret[i] = answer.get(i);
    }

    Arrays.sort(ret);
    return ret;
}

private static Map<String, Integer> getNumOrdersByMenu(
    String[] orders, List<String> combinations) {
    Map<String, Integer> map = new HashMap<>();
    for (String combination : combinations) {
        for (String order : orders) {
            int numIncluded = 0;
            for (int i = 0; i < combination.length(); i++) {
                if (order.contains("" + combination.charAt(i))) {
                    numIncluded++;
                }
            }

            if (numIncluded == combination.length()) {
                map.put(combination, map.getOrDefault(combination, 0) + 1);
            }
        }
    }
    return map;
}

private void findCombinations(String alphabet, int length,
    StringBuilder current, int index, List<String> result) {
    if (current.length() == length) {
        // XY, YX 같은 중복 케이스를 제거하기 위해 정렬 후 집어넣음
        String str = current.toString();
        char[] charArray = str.toCharArray();
        Arrays.sort(charArray);

        result.add(String.valueOf(charArray));
        return;
    }

    for (int i = index; i < alphabet.length(); i++) {
        current.append(alphabet.charAt(i));
        findCombinations(alphabet, length, current, i + 1, result);
        current.deleteCharAt(current.length() - 1);
    }
}