P72411. 메뉴 리뉴얼

문제

제출 코드

• 사용 알고리즘 : 조합
• 각 주문마다 나올 수 있는 코스의 모든 경우를 구해서, TreeMap에 모든 경우에 대한 누적 수를 value로 저장했습니다. 최대 누적 수를 value로 가지는 코스들만 뽑아주면 됩니다.
• 주어지는 주문이 정렬되어 있지 않음을 간과해서 한번 틀렸고, 따로 정렬하는 메소드를 추가해서 해결했습니다.

import java.util.*;

class Solution {
    int count, max;
    String order;
    boolean[] visit;
    SortedMap<String, Integer> menu_list;

    static String sort(String s) {
    	char[] ch = s.toCharArray();
    	Arrays.sort(ch);
    	String str = "";
    	for(char c : ch) str += c;
    	return str;
    }

    void comb(int n, int start){
        if(n==count){
            String s = "";
            for(int i=0; i<visit.length; i++){
                if (visit[i]) s += order.charAt(i);
            }
            if(menu_list.containsKey(s)) {
            	int cnt = menu_list.get(s)+1;
            	max = Math.max(max, cnt);
            	menu_list.replace(s, cnt);
            }
            else menu_list.put(s, 1);
            return;
        }
        for(int i=start; i<order.length(); i++){
            visit[i] = true;
            comb(n+1, i+1);
            visit[i] = false;
        }
    }

    public String[] solution(String[] orders, int[] course) {
        List<String> ans = new ArrayList<String>();

        for(int n : course){
            count = n;
            max = 0;
            menu_list = new TreeMap<String, Integer>();
            for(String od : orders){
                order = sort(od);
                int size = order.length();
                int max = 0;
                visit = new boolean[size];
                comb(0, 0);
            }
            for(String key : menu_list.keySet()) {
            	if(menu_list.get(key) == max) ans.add(key);
            }
        }

        int size = ans.size();
        String[] answer = new String[size];
        for(int i=0; i<size; i++) answer[i] = ans.get(i);
        Arrays.sort(answer);
        return answer;
    }
}