[프로그래머스]level-2 메뉴 리뉴얼 (DFS로 조합 구하기)

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

course 로 주어진 메뉴 개수 만큼의 모든 조합을 구하고

orders 를 돌면서 포함된 조합의 개수를 세고 많은 조합을 구하면 된다.

원하는 개수만큼의 모든 조합을 구하는 로직만 있으면 orders를 순회만 하면 되는 문제임

"AX", "XA" 등은 중복으로 봐야하는 문제이기 때문에 조합을 구하기 전에
문자열을 정렬해주면 이런 중복을 피할 수 있다.

---

DFS 를 이용해서 조합을 구해서 모든 조합을 map 에 담았다.
중복을 제거 할 수 있고 key 가 등장하는 횟수를 카운트 해야하기 때문

map<string, int> m;

void dfs (string s, string com, int idx, int n, int cnt) {
    if (com.length() == n) {
        m[com] = 0;
    }
    
    for (int i = idx; i < s.length(); i++) {
        com[cnt] = s[i];
        dfs(s, com, i + 1, n, cnt + 1);
    }
}

재귀를 이용해서 원래 문자열인 s, 조합이 완성될 com
조합의 길이인 n , dfs의 depth이자 com의 인덱스로 활용할 확인해줄 cnt, idx 가 필요함.

com의 길이가 n 과 같아지면 map 에 저장한다.

그래프로 따지면 최상위 노드는 빈 칸이고
빈칸으로 부터 모든 알파벳이 연결되어있는 상태로 트리가 그려지는 것임.

---

main 에서 dfs 초기 호출하는 부분

for (int n: course) { // 모든 조합 map;
        for (string s: orders) {
            sort(s.begin(), s.end());
            string com = "";
            com.resize(n);
            dfs(s, com, 0, n, 0);
        }
    }

그외에는 map 을 순회하면서 정답을 구하면됨

정답코드

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

using namespace std;

map<string, int> m;

void dfs (string s, string com, int idx, int n, int cnt) {
    if (com.length() == n) {
        m[com] = 0;
    }
    
    for (int i = idx; i < s.length(); i++) {
        com[cnt] = s[i];
        dfs(s, com, i + 1, n, cnt + 1);
    }
}

vector<string> solution(vector<string> orders, vector<int> course) {
    vector<string> answer;
    
    for (int n: course) { // 모든 조합 map;
        for (string s: orders) {
            sort(s.begin(), s.end());
            string com = "";
            com.resize(n);
            dfs(s, com, 0, n, 0);
        }
    }
    
    
    for (auto val: m) {
        for (string s: orders) {
            bool b = true;
            for (int i = 0; i < val.first.length(); i++) {
                if (s.find(val.first[i]) == -1) {
                    b = false;
                    break;
                }
            }
            if (b) {
                m[val.first]++;
            }
        }
    }
    

    
    for(int n: course) {
        int max = 0;
        for (auto val: m) {
            if (val.first.length() == n && val.second > max) {
                max = val.second;
            }
        }
        
        for(auto val: m) {
            if (val.first.length() == n && val.second == max && max > 1) {
                answer.push_back(val.first);
            }
        }
    }
    

    sort(answer.begin(), answer.end());
    return answer;
}