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

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

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

상당히 요구 사항이 많은 문제이다.

처음에 구상만 했을 때는 과연 이게 문제에서 요구하는 시간 내에 해결될지 의문이었으나 도저히 다른 방도가 생각나지 않아서 우선 해봤는데 되더라.. 아무래도 orders 배열의 크기, course 배열의 크기가 최대 각각 20, 10으로 그렇게 크지 않아서 가능한 것 같다.

 

풀이 순서는 크게 아래와 같다.

이중 for loop으로 orders 배열을 course 값마다 순회하며 course의 값만큼 조합을 만들어낸다.

예를들어 ABCFG 주문 내용에서 course = 2인 경우에는 AB, AC, AF, AG, BC, BF, BG... FG라는 조합들을 만든다.

이러한 조합을 만들기 위해 combination이라는 함수를 만들었다.

이는 재귀적인 DFS 라는 전형적인 탐색 방식을 활용하였다.

여기서 불필요한 탐색을 방지하기 위해 만약 탐색 대상인 order 문자열을 넘어서는 인덱스로 탐색을 시도할 시, 현재 시점에서 추가할 수 있는 문자의 개수가 num을 만들기에는 부족할 시에는 종료해버린다.

 

이렇게 만들어진 조합들을 comb에 주문자들의 이름으로 추가한다. 이후에 메뉴 수별로 최대 주문 건수를 len에 구한다.

그 다음에 최대 주문 건수에 해당하는 조합을 오름차순대로 answer 벡터에 추가한다.

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

using namespace std;
map<string, set<int>> comb;
int len[11] = {0};
void combination(string order, string str, int idx, int num, int client) {
    if(str.length() == num) {
        comb[str].insert(client);
        return;
    }
    if(idx >= order.length()) return;
    if(num - str.length() > order.length() - idx) {
        return;
    }
    combination(order, str + order[idx], idx + 1, num, client);
    combination(order, str, idx + 1, num, client);
}

vector<string> solution(vector<string> orders, vector<int> course) {
    vector<string> answer;
    // 각 조합에 대한 총 주문 수 파악
    for(int o = 0;o < orders.size();o++) {
        // orders의 문자열은 정렬 되어있지 않음
        sort(orders[o].begin(), orders[o].end());
        string order = orders[o];
        for(auto i : course) {
            combination(order, "", 0, i, o);
        }
    }
    
    // 유효한 코스요리 메뉴조합의 조건을 조합의 메뉴 수별로 len 배열에 입력
    // (최소 2가지 이상의 단품메뉴 + 메뉴수가 동일한 조합 중 가장 많이 주문된 메뉴 구성)
    for(auto c : comb) {
        if(c.second.size() >= 2 && c.second.size() >= len[c.first.length()]) {
            len[c.first.length()] = c.second.size();
        }
    }
    
    // 위 조건에 부합하는 조합만 추출
    for(auto c : comb) {
        if(len[c.first.length()] == c.second.size()) {
            answer.push_back(c.first);
        }
    }
    
    return answer;
}

주요 사용 method

- set.size()

- string.length()

 

이 문제를 풀면서 오랜만에 DFS를 접하였고, 문제의 요구사항을 어떻게 정리할지를 생각해볼 수 있었다.

문제가 길어서 귀찮더라도 문제의 요구사항을 코드를 작성하기 전에 완벽히 파악하고, 주어진 테스트 케이스를 적용해보며 내가 생각한 풀이 방식이 맞는지 검토를 해봐야 한다.