[코딩테스트] 메뉴 리뉴얼(JAVA)

문제링크 : 2021 KAKAO BLIND RECRUITMENT - 메뉴리뉴얼

아이디어

i번 손님이 주문한 단품메뉴조합(orders[i])에서 2개 메뉴로 구성할 수 있는 가짓수는 nC2개 라고 할 수 있다.
각 손님의 nC2개 경우의 수를 모두 구하고, 가장 자주 나온 경우를 구하면 가장 많이 함께 주문한 단품메뉴들을 구할 수 있다.

1. R = 각 course, 메뉴 구성 개수이다.
2. 각 orders(String이다.) 에서 R개를 뽑아 새로운 subString을 만든다.
3. 모든 orders에 대해 subString을 구했을 때, 가장 많이 나온 subString이 답이 된다.
4. 각 R에 대해 모두 진행한다.

풀이코드

import java.util.*;
class Solution {
    static int maxVal ;
    static Map<String,Integer> map = new HashMap<>();

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

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

	//1. 전체 orders 알파벳 오름차순으로 정렬
        for(int i=0;i<orders.length;i++){
            char[] chars = orders[i].toCharArray();
            Arrays.sort(chars);
            orders[i] = String.valueOf(chars);
        }
	// 2. 전체 course(R번)
        for(int j=0;j<course.length;j++){
            maxVal=1;
            map.clear();
            // 각 orders 에서 R개 뽑은 경우의 수 찾기
            for(int i=0;i<orders.length;i++){
                char[] chars = orders[i].toCharArray();
                boolean[] visit = new boolean[chars.length];
                comb1(chars,visit,0,chars.length,course[j]);
            }
            //주문이 2번이상인 경우에만
            if(maxVal>1){
                for(Map.Entry<String,Integer> entry : map.entrySet()){
               //최댓값을 결과 list에 저장
                    if(entry.getValue() == maxVal){
                        result.add(entry.getKey());
                    }
                }
            }

        }

	
        String[] answer = new String[result.size()];
        for(int k=0;k<result.size();k++){
            answer[k] = result.get(k);
        }
        Arrays.sort(answer); //결과 list sortting
        return answer;
    }


//nCr 구하기
    void comb1(char[] arr, boolean[] visited, int start, int n, int r) {
        if(r == 0) {
            //arr에서 현재 visit에 해당하는 부분을 조합.
            makeStr(arr,visited);
            return;
        } else {
            for(int i = start; i < n; i++) {
                visited[i] = true;
                comb1(arr, visited, i + 1, n, r - 1);
                visited[i] = false;
            }
        }
    }

     void makeStr(char[] arr, boolean[] visit){
        String newStr="";
        for(int i=0;i<arr.length;i++){
            if(visit[i]==true){
                newStr+=arr[i];
            }
        }
	//새로 만든 조합이 이미 map에 있을경우
        if(map.containsKey(newStr)){
            int current = map.get(newStr);
            map.put(newStr,current+1);
            if(current+1>maxVal) //maxVal 저장하기.
                maxVal= current+1;
        }else{
            map.put(newStr,1);
        }
    }
}