[PCCP] Lv2: 메뉴 리뉴얼(72411) 해설

문제

- 문제 링크: 메뉴 리뉴얼

 

해설

- 자료구조: 

- 시간복잡도: 

 

(풀이과정)

1) 

2) 

3) 

4) 

 

코드

(C언어)

solution 1)

solution 1

#include<>

solution 2)

#include<>

solution 3)

#include<>

 

(C++)

solution 1)

#include<>

solution 2)

#include<>

solution 3)

#include<>

 

(C#)

solution 1)

#include<>

solution 2)

#include<>

solution 3)

#include<>

 

(Java)

solution 1)

- N: orders의 길이

- K: course의 최대 크기

- M: orders 원소 하나의 최대 길이

- 이중 반복문을 돌면서 orders의 각 원소를 정렬하고 combinations()를 실행하기 위한 시간 복잡도는 O(K * N * (MlogM + 2^M))

- courseMap에서 최댓값을 찾는 작업: O(N * 2^M)

- 같은 값을 갖는 키 찾기: O(N * 2^M)

- 총 시간 복잡도: O(K * N * (MlogM + 2^M) + 2 * N * 2^M) → O(K * N * MlogM + K * N * 2^M)

- 최종 시간 복잡도: O(N * 2^M)

import java.util.*;

public class Solution {

    // 만들 수 있는 메뉴 구성과 총 주문 수를 저장할 해시맵
    private static HashMap<Integer, HashMap<String, Integer>> courseMap;

    public String[] solution(String[] orders, int[] course) {
        // 해시맵 초기화
        courseMap = new HashMap<>();
        for (int i : course) {
            courseMap.put(i, new HashMap<>());
        }

        // 코스를 배열로 만들고 오름차순 정렬해서 가능한 모든 메뉴 구성을 구함
        for (String order : orders) {
            char[] orderArray = order.toCharArray();
            Arrays.sort(orderArray);
            combinations(0, orderArray, "");
        }

        ArrayList<String> answer = new ArrayList<>();

        // 모든 코스 후보에 대해서
        for (HashMap<String, Integer> count : courseMap.values()) {
            count.values()
                    .stream()
                    .max(Comparator.comparingInt(o -> o)) // 가장 빈도수가 높은 코스를 찾음
                    .ifPresent(cnt -> count.entrySet() // 코스에 대한 메뉴 수가 가능할 때만
                            .stream()
                            // 최소 2명 이상의 손님으로부터 주문된 단품메뉴 조합에 대해서만
                            .filter(entry -> cnt.equals(entry.getValue()) && cnt > 1)
                            // 코스 메뉴만 answer 리스트에 추가
                            .forEach(entry -> answer.add(entry.getKey())));
        }

        Collections.sort(answer); // 오름차순으로 정렬
        return answer.toArray(new String[0]);
    }

    // 만들 수 있는 모든 조합을 재귀 함수를 이용해서 구현
    public static void combinations(int idx, char[] order, String result) {
        // 필요한 코스 메뉴의 수와 일치하는 것만 저장
        if (courseMap.containsKey(result.length())) {
            HashMap<String, Integer> map = courseMap.get(result.length());
            // 해당 코스의 수를 1증가
            map.put(result, map.getOrDefault(result, 0) + 1);
        }

        for (int i = idx; i < order.length; i++) {
            combinations(i + 1, order, result + order[i]);
        }
    }

}

solution 2)

#include<>

solution 3)

#include<>

 

(Python)

solution 1)

- N: orders의 길이

- K: course의 최대 길이

- M: orders 원소 하나의 최대 길이

- 이중 반복문을 돌면서 orders의 각 원소를 정렬하고 combinations()를 실행하기 위한 시간복잡도: O(K*N*(MlogM + 2^M))

- Counters에서 최댓값을 갖는 작업: O(N*(2^M))

- 같은 값을 갖은 키를 찾는 작업: O(N*(2^M))

- 총 시간 복잡도: O(K*N*(MlogM + 2^M) + 2*N*(2^M))

- 최종 시간 복잡도: (K*N*MlogM + K*N*(2^M)) → O(N*(2^M))

from itertools import combinations
from collections import Counter

def solution(orders, course):
    answer = []
    
    for c in course: # 각 코스 요리 길이에 대해
        menu = []
        for order in orders: # 모든 주문에 대해
            comb = combinations(sorted(order), c) # 조합을 이용해 가능한 메뉴 구성을 모두 구함
            menu += comb
        
        counter = Counter(menu) # 각 메뉴 구성이 몇 번 주문되었는지 세어줌
        # 가장 많이 주문된 구성이 1번 이상 주문된 경우
        if (len(counter) != 0 and max(counter.values()) != 1):
            for m, cnt in counter.items():
                if cnt == max(counter.values()): # 가장 많이 주문된 구성을 찾아서
                    answer.append("".join(m)) # 정답 리스트에 추가
                    
    return sorted(answer) # 오름차순 정렬 후 반환

solution 2)

import

solution 3)

import

 

(JavaScript)

solution 1)

- N: orders의 길이

- K: courses의 최대 크기

- M: orders 원소 하나의 최대 길이

- 이중문 반복문을 돌면서 orders의 각 원소를 정렬하고 combinations()를 실행: O(K * N * (MlogM + 2*M))

- counter 오브젝트를 통해 최댓값을 갖는 작업: O(N * 2M)

- 같은 키를 찾는 작업: O(N * 2M)

- 총 시간 복잡도: O(K * N * (MlogM + 2 * M) + 2 * N * 2M)

- 최종 시간 복잡도: O(N * 2 * M)

function combinations(arr, n) {
    if (n === 1) 
        return arr.map((v) => [v]);
    
    const result = [];
    
    arr.forEach((fixed, idx, arr) => {
        const rest = arr.slice(idx + 1);
        const combis = combinations(rest, n - 1);
        const combine = combis.map((v) => [fixed, ...v]);
        result.push(...combine);
    });
    
    return result;
}

function solution(orders, course) {
    const answer = [];
    
    for (const c of course) { // 각 코스 요리 길이에 대해
        const menu = [];
        for (const order of orders) {  // 모든 주문에 대해
            const orderArr = order.split("").sort(); // 주문을 배열로 만든 후 정렬
            // combinations()로 메뉴 구성을 모두 구함
            const comb = combinations(orderArr, c);
            menu.push(...comb);
        }
        
        // 각 메뉴 구성이 몇 번 주문되었는지 세어줌
        const counter = {};
        for (const m of menu) {
            const key = m.join(''); // 배열을 문자열로 변환
            counter[key] = (counter[key] || 0) + 1;
        }
        
        const max = Math.max(...Object.values(counter));
        
        if (max > 1) { // 가장 많이 주문된 구성이 1번 이상 주문된 경우
            for (const [key, value] of Object.entries(counter)) {
                if (value === max) { // 가장 많이 주문된 구성을 찾아서 정답 배열에 추가
                    answer.push(key);
                }
            }
        }
    }

    // 오름차순 정렬 후 반환
    return answer.sort();
}

solution 2)

import

solution 3)

import