와이유스토리

[DFS 조합 반복] 프로그래머스 메뉴 리뉴얼 C++ 본문

코딩테스트/그래프|트리

[DFS 조합 반복] 프로그래머스 메뉴 리뉴얼 C++

유(YOO) 2022. 1. 1. 19:53

 

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

 

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

레스토랑을 운영하던 스카피는 코로나19로 인한 불경기를 극복하고자 메뉴를 새로 구성하려고 고민하고 있습니다. 기존에는 단품으로만 제공하던 메뉴를 조합해서 코스요리 형태로 재구성해서

programmers.co.kr

 

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

using namespace std;

map<string, int> m;
int number[26];

void comb(string order, int idx, string res) {
    if (res.length() > 1) {// 개수 제한X, return 없음, 변수에 결과 저장
        m[res]++;
        number[res.length()-1]=max(number[res.length()-1], m[res]);
    }
    
    for(int i=idx; i<order.size(); i++) {// 시작 번호
        res += order[i];
        comb(order, i + 1, res);
        res.erase(res.length()-1);
    }
}

vector<string> solution(vector<string> orders, vector<int> course) {
    vector<string> answer;
    
    for(int i=0; i<orders.size(); i++) {
        sort(orders[i].begin(), orders[i].end());
        comb(orders[i], 0, "");
    }
    
    for(int i=0; i<course.size(); i++) {
        for(auto mp: m) {
            if (course[i]==mp.first.length()) {
                if ((mp.second>1) && (number[mp.first.length()-1]==mp.second)) {
                    answer.push_back(mp.first);
                }
            }
        }
    }
    
    sort(answer.begin(), answer.end()); // 정렬
    
    return answer;
}
#include <string>
#include <vector>
#include <map>
#include <algorithm>
#include <iostream>

using namespace std;

map<string, int> m; // map
int number[26];

void comb(string order, int depth, int idx, string res) {
    if (depth == 0) { // 개수 제한X, return 없음, 변수에 결과 저장
        m[res]++;
        number[res.length()-1]=max(number[res.length()-1], m[res]);
    }
    
    for(int i=idx+1; i<order.size(); i++) { // 시작 번호
        res += order[i];
        comb(order, depth-1, i, res);
        res.erase(res.length()-1);
    }
}

vector<string> solution(vector<string> orders, vector<int> course) {
    vector<string> answer;
    
    for(int i=0; i<course.size(); i++) {
        for(int j=0; j<orders.size(); j++) {
            sort(orders[j].begin(), orders[j].end()); // 정렬
            comb(orders[j], course[i], -1, "");
        }
    
        for(auto mp: m) {
            if (course[i]==mp.first.length()) {
                if ((mp.second>1) && (number[mp.first.length()-1]==mp.second)) {
                    answer.push_back(mp.first);
                }
            }
        }
    }
    
    sort(answer.begin(), answer.end()); // 정렬
    
    return answer;
}

'코딩테스트 > 그래프|트리' 카테고리의 다른 글

[DFS 단순 반복] 프로그래머스 네트워크 C++  (0) 2022.01.20
[DFS 단순] 프로그래머스 타겟 넘버 C++  (0) 2022.01.20
[DFS, BFS] 백준 12100 2048(Easy) C++  (0) 2022.01.06
[DFS 순열] 프로그래머스 단체사진 찍기 C++  (0) 2021.12.31
[DFS 조합] 프로그래머스 괄호 변환 C++  (0) 2021.12.30
'코딩테스트/그래프|트리' Related Articles more
Comments