[프로그래머스] [Level2] 메뉴 리뉴얼 JAVA

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

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

---

[문제]

[풀이]

탐색+조합+정렬 문제이다 .. 주문마다 구할수 있는 모든 조합을 course의 개수에 맞춰서 뽑아낸다.
그런다음 제일 많이 뽑힌 조합을 카운트해서 리턴 하면된다.

menuMap<메뉴이름 , 뽑힌 횟수> 로 나온 모든 조합을 다 집어 넣는다.
resultMap< course길이, 뽑힌 횟수 > 로 제일 많이 나온 메뉴의 카운트가 몇개 인지 카운팅해서 넣는다.
그런다음 menuMap을 순회하면서 resultMap의 길이당 뽑힌횟수가 크거나 같은것들만 필터링 해서 리턴하면 끝.
이게 level2 라고 .. ?

 

 
import java.util.*;
import java.io.*;
import java.util.stream.*;
 
public class Main {
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        Solution sol = new Solution();
        String[] orders={"ABCFG", "AC", "CDE", "ACDE", "BCFG", "ACDEH"};
        int[] course = {2,3,4};
        System.out.println(Arrays.toString(sol.solution(orders,course)));
 
    }
}
 
class Solution {
    HashMap<String,Integer> menuMap = new HashMap<>();
    HashMap<Integer,Integer> resultMap = new HashMap<>();
    boolean[] visit;
    String[] orderArray;
    int maxDepth;
    public String[] solution(String[] orders, int[] course) {
 
        for (int cnt : course) {
            resultMap.put(cnt,0);
            for (String order : orders) {
 
                if(order.length()<cnt) continue;
 
                visit = new boolean[order.length()];
                orderArray = order.split("");
                Arrays.sort(orderArray);
                maxDepth = cnt;
                for(int i=0;i< orderArray.length;i++){
                    visit[i]=true;
                    dfs(i,1,orderArray[i]);
                    visit[i]=false;
                }
            }
        }
 
        List<String> answer = new ArrayList<>();
 
        menuMap.entrySet().stream()
                .filter(m -> m.getValue() > 1)
                .filter(m->(int)m.getValue()==resultMap.get(m.getKey().length()))
                .forEach(m->answer.add(m.getKey()));
 
        Collections.sort(answer);
        return answer.toArray(new String[0]);
    }
 
    private void dfs(int cur,int depth,String course) {
 
        if(depth==maxDepth){
            if(menuMap.containsKey(course)) menuMap.put(course,menuMap.get(course)+1);
            else menuMap.put(course,1);
 
            if(resultMap.get(depth)<menuMap.get(course)) resultMap.replace(depth, menuMap.get(course));
            return;
        }
        for(int next=cur;next< orderArray.length;next++){
            if(visit[next]) continue;
            visit[next]=true;
            dfs(next,depth+1,course+orderArray[next]);
            visit[next]=false;
        }
    }
}