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

문제

- 문제 링크: 메뉴 리뉴얼

 

코드

(C언어)

solution 1)

#include<>

solution 2)

#include<>

 

(C++)

solution 1)

- N: orders의 길이

- M: course의 길이

- orders의 각 주문을 정렬하는 시간 복잡도는 O(각 order의 길이 * NlogN)이고 각 order의 길이는 최대 10이므로 무시 가능

- course만큼 순회하는 반복문에서 각 order의 조합을 만들 때 시간 복잡도는 O(2^N)

- 조합의 개수만큼 최댓값을 구하는 과정과 가장 많이 주문된 구성을 찾는 과정의 시간 복잡도는 O(2^N)

- course만큼 순회하므로 반복문의 시간 복잡도는 O(M*(2^N)*logM*(2^N))이지만 특정 조건에 맞는 조합이므로 이보다 작음

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

조합 구하기

#include <iostream>
#include <string>

using namespace std;

void combinations(string src, string dst, int depth) {
    if (dst.size() == depth)
        cout << std << endl;
    else
        for (int i = 0; i < src.size(); ++i)
            combination(src.substr(i + 1), dst + src[i], depth);
}

int main(int argc, char** argv) {
    combination("abc", "", 2);
    return 0;
}

 

문제 풀이

#include <algorithm>
#include <string>
#include <vector>
#include <map>

using namespace std;

map<string, int> combi; // 주문의 조합 - 조합의 빈도

// 실제 주문의 조합을 구하는 함수
void combination(string src, string dst, int depth) {
    if (dst.size() == depth) {
        combi[dst]++;
    } else {
        for (int i = 0; i < src.size(); ++i)
            combination(src.substr(i + 1), dst + src[i], depth);
    }
}

vector<string> solution(vector<string> orders, vector<int> course) {
    vector<string> answer;
    // 주문을 오름차순으로 정렬
    for (string& order : orders)
        sort(order.begin(), order.end());
    
    for (int len : course) {
        for (string order : orders) // course 길이별 조합 생성
            combination(order, "", len);
        
        // 각 주문의 빈도수를 순회하면서 가장 많은 빈도수를 maxOrder에 저장
        int maxOrder = 0;
        for (auto it : combi)
            maxOrder = max(maxOrder, it.second);
            
        // 주문 횟수가 2회 이상이면서, 가장 많이 주문된 구성은 answer에 추가
        for (auto it : combi) 
            if (maxOrder >= 2 && it.second == maxOrder)
                answer.push_back(it.first);
                
        combi.clear();
    }
    // 문제의 조건에 따라 주문의 구성을 오름차순 정렬 후 반환
    sort(answer.begin(), answer.end());
    return answer;
}

solution 2)

#include<>

 

(C#)

solution 1)

#include<>

solution 2)

#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<>

 

(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

 

(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