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

문제 링크

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

문제

링크 참조
각 손님들이 주문한 단품메뉴들이 문자열 형식으로 담긴 배열 orders, "스카피"가 추가하고 싶어하는 코스요리를 구성하는 단품메뉴들의 개수가 담긴 배열 course가 매개변수로 주어질 때, "스카피"가 새로 추가하게 될 코스요리의 메뉴 구성을 문자열 형태로 배열에 담아 return 하도록 solution 함수를 완성해 주세요.

제한사항

링크 참조

알고리즘: 브루트 포스, 조합, 구현

풀이

이 문제의 목표는 "스카피"가 새로 추가하게 될 코스요리의 메뉴 구성을 문자열 형태로 배열에 담아 출력하는 문제다.

내가 구현한 방식은 이렇다.

먼저 각 손님이 주문한 단품 메뉴(orders)를 오름차순으로 정렬한다. 왜냐하면 나중에 코스를 식별하기 위함과 answer에 코스를 구성하는 단품 메뉴가 오름차순으로 정렬되기 위해서 (조합을 사용하기 때문에 오름차순은 유지된다.)

"스카피"가 구성하고 싶은 단품 개수(course)를 기준으로 각 손님이 주문한 단품 메뉴(orders)를 조합한다.
예를 들면 2개의 단품 개수로 구성된 코스를 원한다면 각 손님이 주문한 단품 메뉴중 2개를 뽑아 조합한다.
1번 손님) A, B, C, F, G -> AB, AC, AF, AG, BC, BF, BG........

손님의 주문에서 모든 단품 메뉴 조합을 구했다면 모든 요소를 순차 탐색하면서 각 코스마다 주문한 수를 세주고, 코스를 구성하는 개수마다 최대 주문수를 구해준다. 왜냐하면 "스카피"는 가장 많이 주문한 단품 메뉴들로 코스를 구성하기 때문이다.

그리고 코스마다 주문한 수와, 코스를 구성하는 갯수마다 최대 주문수를 구했다면 이제 주문한 수가 2 이상이며, 최대 주문수일 때 코스를 answer에 넣어주면 된다.

시간 복잡도를 계산하면 최대 손님은 20명이고, 단품 메뉴는 손님당 최대 10개, "스카피"가 원하는 course는 10개 이하, 원소 또한 10 이하이기 때문에
(10c1 + 10c2 + 10c3 ... 10c10) * 20으로 약 30,000이다.

• 약 30,000 순차 탐색 + 정렬

소스 코드

import java.util.*;
class Solution {
    static ArrayList<String>[][] combi_orders;
    static ArrayList<Integer> result = new ArrayList<>();
    static HashMap<String, Integer> course_map = new HashMap<>();
    static int[] max_orders = new int[11];
    static ArrayList<String> course_list = new ArrayList<>();
    public String[] solution(String[] orders, int[] course) {
        for(int i=0; i<orders.length; i++) {
            //문자열내 문자를 오름차순 정렬
            char[] charArr = orders[i].toCharArray();
            Arrays.sort(charArr);
            orders[i] = new String(charArr);
        }
        combi_orders = new ArrayList[orders.length][11];
        for(int i=0; i<course.length; i++) {
            for(int j=0; j<orders.length; j++) {
                if(orders[j].length() >= course[i]) DFS(j, course[i], orders[j], 0);
            }
        }
        for(int i=0; i<combi_orders.length; i++) {
            for(int j=0; j<combi_orders[i].length; j++) {
                if(combi_orders[i][j] != null) {
                    for(int k=0; k<combi_orders[i][j].size(); k++) {
                        String course_str = combi_orders[i][j].get(k);
                        if(course_map.get(course_str) == null) course_map.put(course_str, 1);
                        else course_map.put(course_str, course_map.get(course_str) + 1);
                        if(course_map.get(course_str) > max_orders[course_str.length()]) max_orders[course_str.length()] = course_map.get(course_str);
                    }
                }
            }
        }
        course_map.forEach((key, value) -> {
            if(value >= 2 && max_orders[key.length()] == value) course_list.add(key);
        });
        Collections.sort(course_list); //문자열 오름차순 정렬
        String[] answer = new String[course_list.size()];
        for(int i=0; i<course_list.size(); i++) answer[i] = course_list.get(i);
        return answer;
    }
    
    static void DFS(int orders_index, int select_number, String order, int index) {
        if(result.size() == select_number) {
            StringBuilder sb = new StringBuilder();
            for(int i=0; i<result.size(); i++) sb.append(order.charAt(result.get(i)));
            if(combi_orders[orders_index][select_number] == null) combi_orders[orders_index][select_number] = new ArrayList<>();
            combi_orders[orders_index][select_number].add(sb.toString());
            return;
        }
        for(int i=index; i<order.length(); i++) {
            result.add(i);
            DFS(orders_index, select_number, order, i + 1);
            result.remove(result.size() - 1);
        }
    }
}