자바(JAVA) - 메뉴 리뉴얼(Programmers : 72411)

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

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

 

단순한 String관련 문제인 줄 알았으나,, 각 course 길이의 음식 조합을 카운트 하는 게 핵심인 문제였다.

dfs 기반의 combination 함수를 이용하여 가능한 모든 조합을 구할 수 있었다. 

각 코스와 조합된 메뉴의 개수가 동일할 경우 Map에 넣어주며, 중복되는 메뉴들은 value로 카운트 해준 뒤에 value 기준으로 정렬.

정렬된 맵에서 가장 많이 카운트된 조합 + 2명 이상이 주문했는지 확인하며 각 코스에 대한 메뉴 구성을 선택해주면된다.

 

import java.util.*;
class Solution {
    boolean[] visited;
    HashMap<String, Integer> countMap;
    
    public String[] solution(String[] orders, int[] course) {
        ArrayList<String> answerList = new ArrayList<String>();

        for(int c : course) {
            countMap = new HashMap<String, Integer>();
            for(String order : orders) {
                String[] charArr = order.split("");
                Arrays.sort(charArr);
                visited = new boolean[order.length()];
                combination( charArr,0, c);
            }

            List<Map.Entry<String, Integer>> sortedEntries = new LinkedList<Map.Entry<String, Integer>>(countMap.entrySet());
            Collections.sort(sortedEntries, new Comparator<Map.Entry<String,Integer>>() {
                @Override
                public int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2) {
                    return o2.getValue() - o1.getValue();
                }
            });

            int max = 0;
            for(Map.Entry<String, Integer> entry : sortedEntries) {
                int count = entry.getValue();
                if (count > 1 && count >= max) {
                    max = count;
                    answerList.add(entry.getKey());
                }
                if (max != 0 && entry.getValue() < max) {
                    break;
                }
            }
            System.out.println(sortedEntries);
            System.out.println(answerList);
        }
        
        String[] answer = answerList.toArray(new String[answerList.size()]);
        Arrays.sort(answer);
        
        return answer;
    }
    
    public void combination(String[] arr, int ptr, int r) {
        if (r == 0) {
            String combStr = "";
            for (int i = 0; i < arr.length; i++) {
                if (visited[i]) {
                    combStr += arr[i];
                }
            }
            if (countMap.containsKey(combStr)) {
                int count = countMap.get(combStr);
                countMap.replace(combStr, count + 1);
            } else {
                countMap.put(combStr, 1);
            }
        } else {
            for (int i = ptr; i < arr.length; i++) {
                if(!visited[i]) {
                    visited[i] = true;
                    combination(arr,i + 1, r - 1);
                    visited[i] = false;
                }
            }
        }
    }
}