[PGM_72411] 메뉴 리뉴얼 (java)

문제링크

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

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

문제풀이

👨🏻‍💻 핵심 스킬 👨🏻‍💻
브루트포스

사람들의 주문내역이 입력으로 들어온다. 그 주문내역에서 함께 시킨 단품 메뉴들을 확인하여, 가장 많이 함께 시킨 메뉴들을 묶어 세트메뉴를 만들어주는 문제이다. 세트메뉴에 단품메뉴의 개수도 입력으로 주어지게 된다.

 

문제를 해결하기 위하여, 각 사람들이 메뉴를 n가지씩 뽑는 경우의 수를 모두 구하는 메소드를 구현하여주었다. 만약 세트 메뉴에 포함되는 단품의 개수가 2개라면 각 사람들이 주문한 내역을 확인하며 2개씩 묶이는 경우의 수를 모두 구해주고, 다른 사람이 이미 시킨 메뉴라면 값을 1 늘려주는 식으로 문제를 풀었다. 이 때 주의해야할 조건으로 최소 2명이 시킨 메뉴의 조합을 사용해주어야한다. 따라서, 한명이 시킨 메뉴의 조합이 최대라면 그 값은 배제해주어야한다.

 

그리고 마지막으로 다 구하고 나서는 정렬을 한번 하여 오름차순으로 결과값을 정리하여주었다.

구현코드

import java.util.*;

class Solution {
    public String[] solution(String[] orders, int[] course) {
        List<String> answer = new ArrayList<>();
        for(int i = 0; i < course.length; i++){
            Map<String, Integer> menu = new HashMap<>();
            for(int j = 0; j < orders.length; j++){
                boolean[] check = new boolean[orders[j].length()];

                String order = orders[j];
                char[] temp = new char[order.length()];
                for(int idx = 0; idx < temp.length; idx++)
                    temp[idx] = order.charAt(idx);
                Arrays.sort(temp);

                order = "";
                for(char c : temp){
                    order = order + c;
                }

                selectMenu(course[i],0,0,order,check,menu);
            }

            Integer[] values = menu.values().toArray(new Integer[0]);
            int max = Integer.MIN_VALUE;
            for(int val : values){
                if(val > max)
                    max = val;
            }

            if(max > 1) {
                String[] keys = menu.keySet().toArray(new String[0]);
                for (String key : keys) {
                    if (menu.get(key) == max)
                        answer.add(key);
                }
            }
        }

        Collections.sort(answer);
        return answer.toArray(new String[0]);
    }

    public void selectMenu(int menuCount, int selectedMenuCount, int start, String order,boolean[] check,Map<String, Integer> menu){
        if(selectedMenuCount == menuCount){
            String result = "";
            for(int i = 0; i < check.length; i++){
                if(check[i])
                    result = result + order.charAt(i);
            }
            if(menu.containsKey(result)){
                int cnt = menu.get(result) + 1;
                menu.put(result,cnt);
            }
            else
                menu.put(result,1);
            return;
        }

        for(int i = start; i < order.length(); i++){
            check[i] = true;
            selectMenu(menuCount,selectedMenuCount+1,i+1,order,check,menu);
            check[i] = false;
        }

    }
}

잘못된 지식이나 궁금한 내용이 있을 경우 편하게 댓글 남겨주시면 감사하겠습니다 :)