catsridingCATSRIDING|OCEANWAVES
Challenges

Programmers | Level 2 | 메뉴 리뉴얼

jynn@catsriding.com
Sep 09, 2024
Published byJynn
999
Programmers | Level 2 | 메뉴 리뉴얼

Programmers | Level 2 | 메뉴 리뉴얼

Problems

󰧭 Description

레스토랑을 운영하던 스카피는 코로나19로 인한 불경기를 극복하고자 메뉴를 새로 구성하려고 고민하고 있습니다.

기존에는 단품으로만 제공하던 메뉴를 조합해서 코스요리 형태로 재구성해서 새로운 메뉴를 제공하기로 결정했습니다. 어떤 단품메뉴들을 조합해서 코스요리 메뉴로 구성하면 좋을 지 고민하던 "스카피"는 이전에 각 손님들이 주문할 때 가장 많이 함께 주문한 단품메뉴들을 코스요리 메뉴로 구성하기로 했습니다.

단, 코스요리 메뉴는 최소 2가지 이상의 단품메뉴로 구성하려고 합니다. 또한, 최소 2명 이상의 손님으로부터 주문된 단품메뉴 조합에 대해서만 코스요리 메뉴 후보에 포함하기로 했습니다.

예를 들어, 손님 6명이 주문한 단품메뉴들의 조합이 다음과 같다면, (각 손님은 단품메뉴를 2개 이상 주문해야 하며, 각 단품메뉴는 A ~ Z의 알파벳 대문자로 표기합니다.)

손님 번호주문한 단품메뉴 조합
1번 손님A, B, C, F, G
2번 손님A, C
3번 손님C, D, E
4번 손님A, C, D, E
5번 손님B, C, F, G
6번 손님A, C, D, E, H

가장 많이 함께 주문된 단품메뉴 조합에 따라 "스카피"가 만들게 될 코스요리 메뉴 구성 후보는 다음과 같습니다.

코스 종류메뉴 구성설명
요리 2개 코스A, C1번, 2번, 4번, 6번 손님으로부터 총 4번 주문됐습니다.
요리 3개 코스C, D, E3번, 4번, 6번 손님으로부터 총 3번 주문됐습니다.
요리 4개 코스B, C, F, G1번, 5번 손님으로부터 총 2번 주문됐습니다.
요리 4개 코스A, C, D, E4번, 6번 손님으로부터 총 2번 주문됐습니다.

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

 Constraints

  • orders 배열의 크기는 2 이상 20 이하입니다.
  • orders 배열의 각 원소는 크기가 2 이상 10 이하인 문자열입니다.
    • 각 문자열은 알파벳 대문자로만 이루어져 있습니다.
    • 각 문자열에는 같은 알파벳이 중복해서 들어있지 않습니다.
  • course 배열의 크기는 1 이상 10 이하입니다.
    • course 배열의 각 원소는 2 이상 10 이하인 자연수가 오름차순으로 정렬되어 있습니다.
    • course 배열에는 같은 값이 중복해서 들어있지 않습니다.
  • 정답은 각 코스요리 메뉴의 구성을 문자열 형식으로 배열에 담아 사전 순으로 오름차순 정렬해서 return 해주세요.
    • 배열의 각 원소에 저장된 문자열 또한 알파벳 오름차순으로 정렬되어야 합니다.
    • 만약 가장 많이 함께 주문된 메뉴 구성이 여러 개라면, 모두 배열에 담아 return 하면 됩니다.
    • orders와 course 매개변수는 return 하는 배열의 길이가 1 이상이 되도록 주어집니다.

󰦕 Examples

orderscourseresult
["ABCFG", "AC", "CDE", "ACDE", "BCFG", "ACDEH"][2, 3, 4]["AC", "ACDE", "BCFG", "CDE"]
["ABCDE", "AB", "CD", "ADE", "XYZ", "XYZ", "ACD"][2, 3, 5]["ACD", "AD", "ADE", "CD", "XYZ"]
["XYZ", "XWY", "WXA"][2, 3, 4]["WX", "XY"]

Solutions

󰘦 Code

Solution.java
import java.util.*;

class Solution {
    
    // solution 메서드: 주어진 주문 내역(orders)과 코스 크기(course)에 따라 코스 메뉴를 생성하여 반환
    public String[] solution(String[] orders, int[] course) {
        List<String> results = new ArrayList<>();  // 최종 결과를 저장할 리스트
        
        // 각 코스 크기별로 메뉴 조합을 계산
        for (int target : course) {
            Map<String, Integer> combinations = new HashMap<>();  // 조합과 그 빈도를 저장할 맵
            
            // 각 손님의 주문에서 메뉴 조합 생성
            for (String order : orders) {
                char[] menus = order.toCharArray();  // 주문을 문자 배열로 변환
                Arrays.sort(menus);  // 알파벳 순으로 정렬
                order = new String(menus);  // 다시 문자열로 변환
                combine("", order, target, 0, combinations);  // 재귀적으로 조합 생성
            }
            
            // 최대 빈도수 찾기
            int max = 0;  // 최대 빈도수를 저장할 변수
            for (int count : combinations.values()) {
                if (count > 1) max = Math.max(count, max);  // 최소 두 번 이상 등장한 조합 중에서 최댓값 찾기
            }
            
            // 최대 빈도수를 가진 조합들을 결과에 추가
            for (Map.Entry<String, Integer> entry : combinations.entrySet()) {
                if (entry.getValue() == max) results.add(entry.getKey());  // 최대 빈도수를 가진 조합만 추가
            }
        }
        
        // 결과를 사전 순으로 정렬하여 배열로 변환 후 반환
        return results.stream().sorted().toArray(String[]::new);
    }
    
    // combine 메서드: 재귀적으로 메뉴 조합을 생성하고, 그 조합의 빈도를 기록
    private void combine(String comb, String order, int target, int start, Map<String, Integer> combinations) {
        // 목표한 크기의 조합이 완성되면 맵에 저장
        if (comb.length() == target) {
            combinations.put(comb, combinations.getOrDefault(comb, 0) + 1);  // 이미 존재하는 조합이면 빈도 증가
            return;
        }
        
        // 재귀적으로 메뉴를 선택해 조합 생성
        for (int i = start; i < order.length(); i++) {
            combine(comb + order.charAt(i), order, target, i + 1, combinations);  // 다음 메뉴 선택
        }
    }
}

 Approach

이 문제는 각 주문 내역에서 특정 크기의 메뉴 조합을 찾아내고, 가장 많이 주문된 조합을 선택하는 방식입니다. 가능한 모든 조합을 탐색하는 완전 탐색(Brute Force) 방식이 요구됩니다.

1. 문제 분석

레스토랑에서 단품 메뉴들을 조합해 새로운 코스 요리를 구성하려고 합니다. 각 손님의 주문 내역에서 특정 크기의 메뉴 조합을 찾아내고, 여러 손님들이 자주 함께 주문한 조합을 코스 요리 후보로 선정하는 것이 목표입니다.

코스 요리는 두 가지 이상의 메뉴로 구성되며, 동일한 메뉴 조합이 최소 두 명 이상의 손님에게서 주문된 경우에만 후보로 고려됩니다. 예를 들어, 여러 손님이 A와 C를 함께 주문했다면, 그 조합은 코스 요리 후보가 될 수 있습니다. 즉, 손님들의 주문 내역을 분석하여 어떤 메뉴 조합이 자주 등장했는지 파악하는 것이 핵심입니다.

또한, 코스 요리는 다양한 크기의 메뉴 조합으로 구성될 수 있습니다. 두 개의 메뉴로 이루어진 조합, 세 개의 메뉴로 이루어진 조합 등 다양한 크기의 조합을 모두 고려해야 합니다. 동일한 조합이 여러 번 등장할 경우 그 빈도를 계산하고, 가장 많이 등장한 조합을 선택하게 됩니다.

결과적으로, 선택된 메뉴 조합들은 손님들에게 얼마나 인기가 있었는지에 따라 결정되며, 모든 조합은 알파벳 사전순으로 정렬되어야 합니다. 반환되는 결과 역시 사전순으로 정렬된 형태로 출력됩니다. 이 문제의 핵심은 가능한 모든 메뉴 조합을 탐색하고, 그 중 가장 자주 주문된 조합을 찾아내는 것입니다.

2. 접근 방식

이 문제는 손님들의 주문 목록에서 주어진 크기의 메뉴 조합을 찾아내고, 가장 자주 등장한 조합을 선택하는 방식으로 풀 수 있습니다. 구체적인 해결 과정은 다음과 같습니다.

  • 조합 생성: 각 손님의 주문 목록에서 주어진 코스 크기만큼의 메뉴 조합을 생성합니다. 이를 위해 메뉴는 먼저 알파벳 순서대로 정렬된 후, 재귀 함수를 사용해 모든 가능한 조합을 구합니다. 예를 들어, 손님이 A, B, C를 주문했다면, 크기가 2인 조합으로 AB, AC, BC를 만들 수 있습니다. 이 과정에서 재귀적으로 조합을 생성하는 함수가 필요합니다.
  • 빈도 계산: 생성된 조합이 등장할 때마다 그 빈도를 기록합니다. 해시테이블을 사용해 조합을 키로 저장하고, 등장할 때마다 해당 키의 값을 증가시키는 방식으로 빈도를 카운팅합니다. 동일한 조합이 여러 손님의 주문에서 반복되면 그 빈도수를 계속 증가시킵니다.
  • 최대 빈도 조합 추출: 각 코스 크기에 대해 조합이 모두 생성되고 나면, 각 크기에서 가장 많이 등장한 조합을 추출합니다. 이때 최소 2번 이상 등장한 조합들만 유효하며, 그중 최대 빈도를 가진 조합을 선택합니다. 빈도가 같은 여러 조합이 있을 경우 모두 후보로 고려합니다.
  • 정렬 및 반환: 최종적으로 선택된 코스 요리 조합들은 사전 순으로 정렬해야 합니다. 모든 조합은 이미 알파벳 순서로 정렬되어 생성되었으므로, 전체 결과 리스트를 정렬한 후, 배열로 변환하여 반환합니다.

이 과정은 손님들의 주문에서 가능한 모든 조합을 생성하고, 그 빈도를 바탕으로 가장 자주 등장한 조합을 선택하는 방식으로 진행됩니다.

3. 조합 생성 및 빈도 기록

각 손님의 주문 목록에서 특정 크기의 메뉴 조합을 생성하는 작업이 필요합니다. 이를 위해 먼저 각 손님의 주문을 알파벳 순으로 정렬하고, 주어진 크기의 메뉴 조합을 찾습니다. 조합을 생성하는 방식은 재귀 함수를 사용하여, 하나씩 메뉴를 선택하면서 가능한 모든 조합을 만들어냅니다. 조합이 만들어지면 이 조합을 키로, 그로 빈도수를 값으로 하는 Map<K, V>에 저장하고, 해당 조합의 빈도수를 기록합니다.

먼저 각 손님의 주문 내역을 순회하면서 메뉴를 정렬한 후, 재귀적으로 조합을 생성해 나갑니다. 이때 재귀 함수는 현재까지 만들어진 조합을 입력받아, 목표한 크기만큼 조합이 완성될 때까지 계속해서 문자를 추가하는 방식으로 동작합니다.

Solution.java
List<String> results = new ArrayList<>(); // 최종 결과를 저장할 리스트

for (int target : course) {  // 코스 크기별로 처리
    Map<String, Integer> combinations = new HashMap<>();  // 각 코스 크기에 대한 조합을 저장
    
    for (String order : orders) {  // 각 손님의 주문 내역을 순회
        char[] menus = order.toCharArray();  // 주문 내역을 문자 배열로 변환
        Arrays.sort(menus);  // 알파벳 순으로 정렬
        order = new String(menus);  // 다시 문자열로 변환
        combine("", order, target, 0, combinations);  // 재귀적으로 조합 생성 및 빈도 기록
    }
    
    ...
}

조합을 생성하는 combine() 함수는 재귀적으로 호출되며, 각 메뉴를 선택해 조합을 만들어 나갑니다. 목표한 길이만큼의 조합이 완성되면, 해당 조합을 Map<K, V>에 저장하고 그 빈도를 기록합니다. 각 호출마다 선택된 문자는 조합에 추가되며, 선택된 문자를 제외한 나머지 문자들로 다음 조합을 만들어 나갑니다.

Solution.java
private void combine(
        String comb,         // 현재까지 만들어진 메뉴 조합
        String order,        // 손님의 정렬된 전체 주문 목록
        int target,          // 목표로 하는 조합의 길이 (코스 메뉴 개수)
        int start,           // 다음에 선택할 메뉴의 시작 인덱스
        Map<String, Integer> combinations  // 조합과 그 빈도를 저장하는 Map
) {
    // 목표한 크기의 조합이 완성되면 이를 Map에 기록
    if (comb.length() == target) {
        combinations.put(comb, combinations.getOrDefault(comb, 0) + 1);  // 조합이 이미 존재하면 빈도 증가
        return;
    }
    
    // 재귀적으로 메뉴를 선택하며 조합 생성
    for (int i = start; i < order.length(); i++) {
        combine(comb + order.charAt(i), order, target, i + 1, combinations);  // 다음 메뉴 선택
    }
}

이 함수는 각 조합이 완성될 때마다 해당 조합을 Map<K, V>에 저장하여, 나중에 빈도 계산을 쉽게 할 수 있도록 합니다. 조합의 길이가 목표한 크기에 도달하면 더 이상 추가적인 메뉴 선택을 하지 않고, 빈도를 기록한 후 종료합니다.

4. 최대 빈도 조합 계산 및 결과 추가

각 코스 크기에 맞는 모든 조합이 생성되고, 해당 조합들의 빈도수가 Map<K, V>에 저장되면, 이제 그중에서 가장 자주 등장한 조합을 찾아야 합니다. 이 과정에서는 각 코스 크기에 대해 빈도수가 가장 높은 조합을 선택합니다. 중요한 점은 최소 두 번 이상 주문된 조합만이 유효하므로, 빈도가 2 이상인 조합들 중에서 최댓값을 찾아야 합니다. 이후, 동일한 빈도를 가진 다른 조합들도 모두 결과에 포함시킵니다.

먼저 combinations 맵을 순회하면서 각 조합의 빈도를 확인하고, 그중 최대 빈도를 찾아냅니다. 최대 빈도를 찾는 과정에서 최소 두 번 이상 등장한 조합만 고려합니다.

Solution.java
for (int target : course) {
    ...
    
    int max = 0;  // 최대 빈도수를 저장할 변수 초기화
    
    // 각 조합의 빈도를 확인하여 최대 빈도를 찾음
    for (int count : combinations.values()) {
        if (count > 1) {  // 최소 두 번 이상 등장한 조합만 고려
            max = Math.max(count, max);  // 현재 빈도와 기존 최대 빈도 비교
        }
    }
}

최대 빈도를 찾은 후, 다시 combinations 맵을 순회하면서, 그 빈도가 최대인 조합들을 모두 결과 리스트에 추가합니다. 여러 조합이 동일한 빈도를 가질 수 있기 때문에, 조건에 맞는 모든 조합을 저장해야 합니다.

Solution.java
for (int target : course) {
    ...
    
    // 최대 빈도를 가진 조합을 결과 리스트에 추가
    for (Map.Entry<String, Integer> entry : combinations.entrySet()) {
        if (entry.getValue() == max) {
            results.add(entry.getKey());  // 빈도가 최대인 조합을 결과에 추가
        }
    }
}
5. 최종 결과 정렬 및 반환

모든 코스 크기에서 최대 빈도를 가진 조합들이 리스트에 무작위로 추가된 상태입니다. 이제 이 리스트를 사전 순으로 정렬한 후, 배열로 변환하여 반환해야 합니다. 문제의 요구 사항에 따라 결과는 반드시 사전 순으로 정렬된 상태여야 하므로, 반환하기 전에 리스트를 정렬하는 과정이 필요합니다. 먼저 리스트에 담긴 조합들을 sorted() 메서드를 사용해 사전 순으로 정렬하고, 정렬이 완료된 후 toArray() 메서드를 사용하여 리스트를 배열로 변환하여 최종적으로 반환합니다.

Solution.java
// 결과 리스트를 사전 순으로 정렬한 후 배열로 변환하여 반환
return results.stream()
        .sorted()
        .toArray(String[]::new);

󰄉 Complexity

  • ⏳ TC: O(n * 2^m)
  • 💾 SC: O(n)

이 문제의 시간 복잡도는 각 손님의 주문에서 가능한 모든 메뉴 조합을 구하는 과정에서 발생합니다. 한 주문에 포함된 메뉴가 m개일 경우, 해당 주문에서 생성할 수 있는 모든 조합의 수는 2^m입니다. 이를 n개의 주문에 대해 반복하여 처리하므로, 전체 시간 복잡도는 O(n * 2^m)이 됩니다. 공간 복잡도는 생성된 조합을 저장하는 데 필요한 메모리와 관련이 있습니다. 각 주문에서 최대 2^m개의 조합이 발생할 수 있으며, 결과는 n개의 주문에 비례하게 저장되므로, 전체 공간 복잡도는 O(n)입니다.

  • Algorithm
  • Brute Force