2021 KAKAO BLIND RECRUITMENT - 메뉴 리뉴얼

Java

2021 KAKAO BLIND RECRUITMENT - 메뉴 리뉴얼

문제

문제 출처

접근 방법

orders 배열의 각 원소는 크기가 2 이상 10 이하인 문자열이므로, 각 손님들이 주문한 메뉴 들로 모두 조합을 하여도 시간 내 해결이 가능하다.
course 개수 만큼 모든 조합을 구한 뒤 그 조합의 개수를 Map으로 센다.

Map의 value(개수)를 기준으로 내림 차순으로 졍렬하여, 많이 주문된 메뉴 구성을 구한다.

코드

import java.util.*;
import java.util.Map.Entry;

class Solution {
    static Map<String, Integer> menu;
	static char sel[];

	static int n, size;
    public static String[] solution(String[] orders, int[] course) {
        String[] answer = {};
        ArrayList<String> result = new ArrayList<>();
        for(int len : course) {

        	menu = new HashMap<>();
        	size = len;
        	sel = new char[size];
        	for(String str : orders) {
        		n = str.length();
        		DFS(0,0,str);
        	}

        	List<Entry<String, Integer>> list = new ArrayList<>(menu.entrySet());  // Map을 내림 차순으로 정렬한다.
        	Collections.sort(list, (o1,o2)->{
        		return -o1.getValue().compareTo(o2.getValue()); // Map의 value를 기준으로 정렬한다.
        	});

        	if(list.isEmpty() || list.get(0).getValue() < 2)	// 손님은 단품메뉴를 2개 이상 주문해야 하므로, 예외 조건
        		continue;

        	int maxN = list.get(0).getValue();

        	for(Entry<String, Integer> en : list) {	// 가장 많이 함께 주문된 메뉴 구성이 여러 개일 때
        		if(en.getValue() != maxN)
        			break;
        		result.add(en.getKey());
        	}
        }

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

    static void DFS(int lv, int start, String order) {
    	if(lv == size) {
    		char[] cl = sel.clone();
    		Arrays.sort(cl);					// AC 아 CA가 다른 경우를 방지하기 위해, 오름차순 정렬한다.
    		String str = String.valueOf(cl);	// 뽑은 단품 메뉴들로 조합을 만든다.

    		if(menu.containsKey(str))			// 메뉴 조합의 개수를 센다
    			menu.put(str, menu.get(str) + 1);
    		else
    			menu.put(str, 1);

    		return;
    	}

    	for(int i = start; i < n; i++) {
    		sel[lv] = order.charAt(i);
    		DFS(lv + 1, i + 1, order);
    	}
    }
}

후기 및 개선할 점