22.12.01 - [PG] 메뉴 리뉴얼

[suhyunsim]

문제

• 메뉴 리뉴얼

핵심 아이디어

어려운 점, 실수

• 조합 관련 재귀함수 부분 이해를 못했음

풀이

package main.java.com.poogle.PG.Q72411;

import java.util.*;

public class Solution {
    public static void main(String[] args) {
        System.out.println(Arrays.toString(solution(new String[]{"ABCFG", "AC", "CDE", "ACDE", "BCFG", "ACDEH"}, new int[]{2, 3, 4})));
        System.out.println(Arrays.toString(solution(new String[]{"ABCDE", "AB", "CD", "ADE", "XYZ", "XYZ", "ACD"}, new int[]{2, 3, 5})));
        System.out.println(Arrays.toString(solution(new String[]{"XYZ", "XWY", "WXA"}, new int[]{2, 3, 4})));
    }

    static List<String> answerList = new ArrayList<>();
    static Map<String, Integer> map = new HashMap<>();

    private static String[] solution(String[] orders, int[] course) {
        //1. 각 order 정렬
        for (int i = 0; i < orders.length; i++) {
            char[] arr = orders[i].toCharArray();
            Arrays.sort(arr);
            orders[i] = String.valueOf(arr);
        }

        //2. 각 order를 기준으로 course length만큼의 조합 만들기
        for (int courseLength : course) {
            for (String order : orders) {
                combination("", order, courseLength);
            }
            //3. 가장 많은 조합 저장
            if (!map.isEmpty()) {
                List<Integer> countList = new ArrayList<>(map.values());
                int max = Collections.max(countList);
                if (max > 1)
                    for (String key : map.keySet()) {
                        if (map.get(key) == max)
                            answerList.add(key);
                    }
                map.clear();
            }
        }
        Collections.sort(answerList);
        String[] answer = new String[answerList.size()];
        for (int i = 0; i < answer.length; i++) {
            answer[i] = answerList.get(i);
        }
        return answer;
    }

    /*
    order: 현재까지 조합된 코스
    others: 아직까지 사용되지 않은 알파벳
    cnt: 몇 개를 더 조합해야 되는지
     */
    private static void combination(String order, String others, int cnt) {
        //탈출조건
        if (cnt == 0) {
            map.put(order, map.getOrDefault(order, 0) + 1);
            return;
        }
        //수행동작 0 ~length
        for (int i = 0; i < others.length(); i++) {
            combination(order + others.charAt(i), others.substring(i + 1), cnt - 1);
        }
    }
}