[프로그래머스] 메뉴 리뉴얼 - Java

문제 설명

 

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

 

풀이 회고

해당 문제를 풀기 위해 접근한 방법으로는 다음과 같습니다.

 

1. DFS를 이용하여 손님들이 주문한 메뉴들(String[] orders)로부터 구성 가능한 메뉴의 조합을 구합니다.

 - 이때 조합의 개수는 문제에서 주어지는 단품 메뉴 개수(int[] course)를 이용하여 정합니다.

2. HashMap을 이용하여 메뉴의 조합별 개수를 카운팅(counting))합니다.

3. 가장 많이 조합되었던 메뉴의 조합을 탐색합니다.

 

우선 특정 손님이 주문한 메뉴(String order)를 문자열 배열(String[] menus)로 분리했습니다. 이는 문제에서 메뉴 조합을 사전순으로 구성하도록 요구하고 있기 때문에 메뉴를 조합할 때 사전순으로 조합하기 위함입니다. (매개변수로 주어지는 메뉴(String order)들은 사전순으로 되어있지 않을 수 있습니다.)

 

            for (String order : orders) {
                (... 생략 ...)
                String[] menus = order.split("");
                Arrays.sort(menus); // 메뉴들을 사전순으로 정렬
                (... 생략 ...)
            }

 

이제 DFS를 통해 분리한 문자열 배열(String[] menus)로부터 메뉴의 조합을 구합니다. 이때 DFS 함수의 파라미터로는 depth(int), cnt(int), sizeOfCourse(int), 손님이 주문한 메뉴들인 menus(String[]), 조합 구성을 위한 boolean형 배열 choicesOfMenu(boolean[])를 지니고 있습니다.

 

depth의 경우 주어진 메뉴 범위를 넘어 탐색하는 것을 방지하도록 해주며, cnt는 메뉴 조합의 개수를 의미합니다. cnt가 sizeOfcourse(문제에서 주어지는 단품 메뉴 개수 int[] course 중 하나)와 같으면 메뉴 조합이 다 구성된 것으로 볼 수 있습니다.

 

마지막으로 menus와 choicesOfMenu는 메뉴 조합을 구성할 때 사용되는 배열입니다. choicesOfMenu의 특정 요소가 true 값이면 해당 메뉴를 선택했다는 것과 동일한 의미를 가집니다. 이를 통해 menus의 요소로부터 메뉴 조합을 구할 수 있습니다. 이때 getMenuCombination 메서드 이용하며 HashMap을 이용하여 해당 메뉴 조합의 개수를 카운팅합니다.

 

    Map<String, Integer> countByMenuCombination = new HashMap<>();
    
    (... 생략 ...)

    public void dfs(int depth, int cnt, int sizeOfCourse, String[] menus, boolean[] choicesOfMenu) {
        if (cnt == sizeOfCourse) {
            String menuCombination = getMenuCombination(menus, choicesOfMenu);
            countByMenuCombination.put(menuCombination, countByMenuCombination.getOrDefault(menuCombination, 0) + 1);
            return;
        }

        if (depth == menus.length) {
            return;
        }

        choicesOfMenu[depth] = true;
        dfs(depth + 1, cnt + 1, sizeOfCourse, menus, choicesOfMenu);
        choicesOfMenu[depth] = false;
        dfs(depth + 1, cnt, sizeOfCourse, menus, choicesOfMenu);
    }
    
    public String getMenuCombination(String[] menus, boolean[] visited) {
        StringBuilder sb = new StringBuilder();

        for (int i = 0; i < menus.length; i++) {
            if (visited[i]) {
                sb.append(menus[i]);
            }
        }

        return sb.toString();
    }

 

이제 메뉴 조합과 메뉴 조합별 개수를 구했으므로 손님들의 주문으로부터 메뉴 조합의 크기(int[] course에 의한) 내에서 메뉴 조합들 중 가장 많이 조합되었던 수(maxCountOfOrder)를 찾습니다. 이때 스트림을 활용했는데, 특정 메뉴 조합의 크기(int[] course에 의한) 내에서 그리고 메뉴 조합별 개수가 최소 2개 이상인 요소들을 선별하여 가장 많이 조합되었던 수(maxCountOfOrder)를 구했습니다. (문제에서는 최소 2명 이상의 손님으로부터 주문단 단품 메뉴 조합에 대해서만 코스요리 메뉴 후보에 포함하기로 하고있습니다.)

 

이후 다시 스트림을 활용하여 방금 전 구한 maxCountOfOrder의 값과 일치하는 메뉴 조합들을 선별합니다. 해당 작업을 마친 이후에는 int[] course 요소 중 다른 메뉴 조합의 크기를 통해 위 작업을 반복합니다. 최종적으로 모두 구한 메뉴 조합들을 사전순으로 정렬(문제 요구사항)하여 문자열 배열로 변환한 후 결과값으로 반환합니다.

 

    public String[] solution(String[] orders, int[] course) {
    
        List<String> result = new ArrayList<>();
        
        for (int sizeOfCourse : course) {
        
            (... 생략 ...)
        
            int maxCountOfOrder = countByMenuCombination.keySet().stream()
                .filter(menuCombination -> menuCombination.length() == sizeOfCourse)
                .map(menuCombination -> countByMenuCombination.get(menuCombination))
                .filter(count -> count > 1).mapToInt(x -> x)
                .max().orElse(0);
            result.addAll(
                countByMenuCombination.keySet().stream()
                    .filter(menuCombination -> menuCombination.length() == sizeOfCourse && countByMenuCombination.get(menuCombination) == maxCountOfOrder)
                    .collect(Collectors.toList())
            );
        }

        Collections.sort(result);

        return result.toArray(new String[0]);

 

전체 소스 코드

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.stream.Collectors;

class Solution {

    Map<String, Integer> countByMenuCombination = new HashMap<>();

    public String[] solution(String[] orders, int[] course) {

        List<String> result = new ArrayList<>();

        for (int sizeOfCourse : course) {
            for (String order : orders) {
                String[] menus = order.split("");
                boolean[] choicesOfMenu = new boolean[menus.length];
                Arrays.sort(menus);
                dfs(0, 0, sizeOfCourse, menus, choicesOfMenu);
            }

            int maxCountOfOrder = countByMenuCombination.keySet().stream()
                .filter(menuCombination -> menuCombination.length() == sizeOfCourse)
                .map(menuCombination -> countByMenuCombination.get(menuCombination))
                .filter(count -> count > 1).mapToInt(x -> x)
                .max().orElse(0);
            result.addAll(
                countByMenuCombination.keySet().stream()
                    .filter(menuCombination -> menuCombination.length() == sizeOfCourse && countByMenuCombination.get(menuCombination) == maxCountOfOrder)
                    .collect(Collectors.toList())
            );
        }

        Collections.sort(result);

        return result.toArray(new String[0]);
    }

    public void dfs(int depth, int cnt, int sizeOfCourse, String[] menus, boolean[] choicesOfMenu) {
        if (cnt == sizeOfCourse) {
            String menuCombination = getMenuCombination(menus, choicesOfMenu);
            countByMenuCombination.put(menuCombination, countByMenuCombination.getOrDefault(menuCombination, 0) + 1);
            return;
        }

        if (depth == menus.length) {
            return;
        }

        choicesOfMenu[depth] = true;
        dfs(depth + 1, cnt + 1, sizeOfCourse, menus, choicesOfMenu);
        choicesOfMenu[depth] = false;
        dfs(depth + 1, cnt, sizeOfCourse, menus, choicesOfMenu);
    }

    public String getMenuCombination(String[] menus, boolean[] visited) {
        StringBuilder sb = new StringBuilder();

        for (int i = 0; i < menus.length; i++) {
            if (visited[i]) {
                sb.append(menus[i]);
            }
        }

        return sb.toString();
    }
}

 

 

참고자료

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