[알고리즘 / 프로그래머스] 메뉴 리뉴얼

programmers.co.kr/learn/courses/30/lessons/72411

코딩테스트 연습 - 메뉴 리뉴얼

 

문제는 위와 같으며, 조합을 구해서 해결할 수 있는 문제였습니다.

 

1. 주어진 course 배열의 숫자만큼 코스 요리의 메뉴를 구성하기 때문에, course 배열을 반복하면서 몇개의 메뉴(A)로 코스를 결정할지 정하고

 

orders = ["ABCFG", "AC", "CDE", "ACDE", "BCFG", "ACDEH"]

course = [2, 3, 4]

 

2. 전체 주문 배열을 돌면서 각 주문에서 A개씩 묶을 수 있는 조합을 모두 구합니다.

 

3. 구한 코스메뉴 구성을 오름차순 정렬한 뒤, Map 에 저장합니다. 이때 코스메뉴명을 키로 하고 해당 코스메뉴가 나온 횟수를 값으로 저장합니다.

 

2개씩 코스메뉴를 구성한다면?

menus = {"AB": 1, "BC": 2, "FG": 2, "CD": 3, "DE"; 3, "AC": 4, "CE": 3, "CF": 2, "AD": 2, "EH": 1, "BF": 2, "CG": 2, "AE": 2, "DH": 1, "AF": 1, "BG": 2, "CH": 1, "AG": 1, "AH": 1}

 

4. A개씩 묶은 메뉴 구성을 모두 확인했다면, 이들 중 가장 많이 나온 구성을 찾아 answer 배열에 저장합니다.

 

answer = ["AC"]

 

5. 2~4 과정을 반복하면서 course 배열에 주어진 수만큼 모두 확인하면 answer 배열을 반환합니다.

 

3개씩 코스메뉴를 구성한다면?

menus = {"ABC": 1, "AFG": 1, "BFG": 2, "ACD": 2, "ADE": 2, "ACE": 2, "ACF": 1, "BCF": 2, "AEH": 1, "ABF": 1, "ACG": 1, "CFG": 2, "CDE": 3, "ADH": 1, "ABG": 1, "ACH": 1, "CDH": 1,"DEH": 1, "BCG": 2, "CEH": 1}

 

answer = ["AC", "CDE"]

 

4개씩 코스메뉴를 구성한다면?

menus = {"ACDH": 1, "ADEH": 1, "ABCF": 1, "ABCG": 1, "ACEH": 1, "CDEH": 1, "ABFG": 1, "ACFG": 1, "BCFG": 2, "ACDE": 2}

 

answer = ["AC", "CDE", "BCFG", "ACDE"]

 

최종 answer = ["AC", "ACDE", "BCFG", "CDE"]

---

코드를 살펴보면 다음과 같습니다.

import java.util.*;

class Solution {
    private static Map<String, Integer> menus;
    
    public String[] solution(String[] orders, int[] course) {
        ArrayList<String> answer = new ArrayList<>();
        // course 배열을 반복하며 c개씩 묶을 수 있는 모든 메뉴 조합을 구합니다.
        for (int c : course) {
            // c개씩 묶을 수 있는 모든 메뉴 조합을 저장합니다. (키: 코스메뉴명, 값: 해당 코스메뉴가 주문된 수)
            menus = new HashMap<>();
            // 주어진 모든 주문을 확인하면서
            for (String order : orders) {
                // 각 주문을 c개씩 묶을 수 있는 조합을 구합니다.
                if (order.length() >= c) {
                    combi(order, new boolean[order.length()], 0, c, c);
                }
            }

            // 뽑힌 코스메뉴 중 가장 주문이 많이 된 코스메뉴 구하기 (최소 2번 이상)
            int maxNum = 2;
            ArrayList<String> tmp = new ArrayList<>();
            for (Map.Entry<String, Integer> menu : menus.entrySet()) {
                if (menu.getValue() > maxNum) {
                    tmp.clear();
                    maxNum = menu.getValue();
                    tmp.add(menu.getKey());
                } else if (menu.getValue() == maxNum) {
                    tmp.add(menu.getKey());
                }
            }

            // 결과 저장하기
            answer.addAll(tmp);
        }

        // 최종 코스메뉴 오름차순으로 정렬하고 반환하기
        Collections.sort(answer);
        return answer.toArray(new String[answer.size()]);
    }
    
    // 주어진 문자열에서 각 문자를 r개 선택하기 (조합구하기)
    private static void combi(String text, boolean[] visited, int start, int r, int cnt) {
        if(r == 0) {
            char[] selectedChar = new char[cnt];
            int idx = 0;
            // 뽑힌 문자 저장하기
            for (int i = 0; i < visited.length; i++) {
                if (visited[i]) {
                    selectedChar[idx] = text.charAt(i);
                    idx += 1;
                }
            }

            // 구성된 코스 메뉴 오름차순으로 정렬하기
            Arrays.sort(selectedChar);

            // 해당 코스 메뉴와 해당 메뉴가 나온 수를 저장
            String key = String.valueOf(selectedChar);
            if (menus.containsKey(key)) {
                menus.put(key, menus.get(key) + 1);
            } else {
                menus.put(key, 1);
            }
        } else {
            for(int i = start; i < visited.length; i++) {
                visited[i] = true;
                combi(text, visited, i + 1, r - 1, cnt);
                visited[i] = false;
            }
        }
    }
}