프로그래머스 - 불량 사용자 [C++]

 이 문제는 백트래킹과 맵을 이용해서 풀었다. solution의 첫 for문은 각 banned_id에 부합하는 user_id를 찾아내는 것이고, solve 함수는 이를 기반으로 백트래킹을 돌려 해당 조합이 사용되었는지 확인한 후, 사용되지 않았으면 1을 리턴하는 것이다. 입력의 크기가 user_id, banned_id 모두 8 이하로 매우 작아 완전 탐색으로 가능한 문제였다.

 

 

 

 

 

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

using namespace std;

vector<int> banned_list[8];
map<vector<int>, int> listUsed;
bool userUsed[8];

int solve(vector<int> ban, int bannedSize, int bannedIndex) {
    if (ban.size() == bannedSize) {
        sort(ban.begin(), ban.end());
        
        if (listUsed[ban] == 0) {
            listUsed[ban]++;
            return 1;
        }
        else {
            return 0;
        }
    }
    
    int result = 0;
    for (int& banned : banned_list[bannedIndex]) {
        if (!userUsed[banned]) {
            userUsed[banned] = true;
            ban.push_back(banned);
            result += solve(ban, bannedSize, bannedIndex + 1);
            ban.pop_back();
            userUsed[banned] = false;
        }
    }
    return result;
}

int solution(vector<string> user_id, vector<string> banned_id) {
    int answer = 0;
    
    // banned_list 채우기
    for (int b = 0; b < banned_id.size(); b++) {
        string& banned = banned_id[b];
        
        for (int u = 0; u < user_id.size(); u++) {
            string& user = user_id[u];
            
            if (user.size() != banned.size()) {
                continue;
            }
            
            int size = banned.size();
            bool flag = true;
            for (int i = 0; i < size; i++) {
                if (banned[i] == '*') {
                    continue;
                }
                if (banned[i] != user[i]) {
                    flag = false;
                    break;
                }
            }
            
            if (flag) {
                banned_list[b].push_back(u);
            }
        }
    }
    
    vector<int> ban;
    answer = solve(ban, banned_id.size(), 0);
    
    return answer;
}