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

해당 문제 링크

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

해결방법

위에 제한사항으로 볼때 시작복잡도는 O(n^2)가 되어도 상관없을듯 하여 백트래킹 기법을 사용해서 무든 주문의 조합을 저장해서 가장 많은 갯수의 조합을 뽑아내는 방식을 생각했다.

1. course의 갯수만큼 모든 order의 주문 조합을 뽑아낸다.
2. 주문 조합이 2개 이상인 조합만 추려낸다.
3. course별로 가장 조합이 많은 갯수만 추려낸다.
4. 오름차순으로 정렬한다.

소스코드

	private Map<String, Integer> map = new HashMap<>();

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

        for (int count : course) {
            for (String order : orders) {
                if (order.length() >= count) {
                	// order가 순서가 오름차순이 아니라서 정렬해줌.
                    char[] chars = order.toCharArray();
                    Arrays.sort(chars);
                    order = new String(chars);
					
                    // 1. course의 갯수만큼 모든 order의 주문 조합을 뽑아낸다.
                    DFS(order, "", 0, count);
                }
            }
        }
        // 2. 주문 조합이 2개 이상인 조합만 추려낸다.
        List<Map.Entry<String, Integer>> list = map.entrySet()
                .stream()
                .filter(e -> e.getValue() > 1)
                .collect(Collectors.toList());

        List<String> result = new ArrayList<>();
        for (int count : course) {
        	// 3. course별로 가장 조합이 많은 갯수만 추려낸다.
            List<Map.Entry<String, Integer>> countMatchList = list.stream()
                    .filter(e -> e.getKey().length() == count)
                    .collect(Collectors.toList());

            int max = countMatchList.stream()
                    .map(Map.Entry::getValue)
                    .max(Comparator.comparingInt(o -> o))
                    .orElse(0);

            List<String> maxList = countMatchList.stream()
                    .filter(e -> e.getValue() == max)
                    .map(Map.Entry::getKey)
                    .collect(Collectors.toList());

            result.addAll(maxList);
        }

		// 4. 오름차순으로 정렬한다.
        Collections.sort(result);
        int arrListSize = result.size();
        return result.toArray(new String[arrListSize]);
    }

    public void DFS(String str, String temp, int index, int size) {
        if (temp.length() == size) {
            int count = map.getOrDefault(temp, 0);
            map.put(temp, count + 1);
            return;
        }

        for (int i = index; i < str.length(); i++) {
            temp += str.charAt(i);
            DFS(str, temp, i + 1, size);
            temp = temp.substring(0, temp.length() - 1);
        }
    }

어려웠던 점

처음에 떠올렸던 방식은 한 사람의 주문을 다른사람들의 주문과 하나씩 다 비교해가면서 course갯수 만큼 주문한 오더를 찾으려고 했지만 for중첩이 너무 많아지는것같아서 고민을 하던중에 차라리 그냥 모든 조합을 다 저장시키고 제일 많은 조합을 구해보자 라는 생각으로 구현했다. 모든 조합을 다 구현하면 제한사항에 따라서 최악의 기준으로 작동 횟수를 계산해보니 10^2(orders 원소의 최대 크기 * orders 원소의 최대 크기) * 20(orders배열의 최대 크기) * 10(course배열의 최대 크기) = 20000이기 때문에 충분하다고 판단 후 작성했다.