프로그래머스 메뉴 리뉴얼 - Java

프로그래머스 2021 KAKAO BLIND RECRUITMENT 2번 문제 메뉴 리뉴얼

처음 문제를 풀때 반대의 방향으로 접근을 하여 시간이 더욱 소요 되었다. 

 

먼저 이 문제는 부르트포스 알고리즘을 통해 해결한다.

 

주문한 모든 메뉴들의 조합을 각각 구한 뒤, 기록을 해두고 가장 많은 조합을 찾으면 된다.

생각보다 단순한 논리였다.

 

import java.util.*;

class Solution {
      HashMap<String, Integer> hashMap = new HashMap<>();

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

        ArrayList<String> before = new ArrayList<>(); // 초기화
        StringBuilder sb = new StringBuilder();

        for (String menu : orders) {
            char[] tmp = menu.toCharArray();
            Arrays.sort(tmp);
            for (int i : course) {
                Comb(tmp, sb, 0, 0, i);
            }
         } // 각각의 조합을 만들어 둠.

        for (int i : course) {
            Set<Map.Entry<String, Integer>> entry2 = hashMap.entrySet();

            int max = 0;
            for (Map.Entry<String, Integer> entry : entry2) {
                if (entry.getKey().length() == i) {
                    max = Math.max(max, entry.getValue());
                }
            }
            for (Map.Entry<String, Integer> entry : entry2) {
                if (max > 1 && entry.getValue() == max && entry.getKey().length() == i)
                    before.add(entry.getKey());
            }
        }

        Collections.sort(before);
        String[] answer = new String[before.size()];

        for (int i = 0; i < before.size(); i++) {
            answer[i] = before.get(i);
        }

        return answer;
    }

    public void Comb(char[] order, StringBuilder sb, int start, int n, int r) {
        if (n == r) {
            hashMap.put(sb.toString(), hashMap.getOrDefault(sb.toString(), 0) + 1);
            return;
        }
        for (int i = start; i < order.length; i++) {
            sb.append(order[i]);
            Comb(order, sb, i + 1, n + 1, r);
            sb.delete(n, n + 1);
        }
    }
}