[C++] 2019 카카오 개발자 겨울 인턴십 - 불량 사용자

 

 

https://school.programmers.co.kr/learn/courses/30/lessons/64064

프로그래머스

 

 

 

#include <bits/stdc++.h>


bool used[8];
int answer;
std::unordered_set<std::string> only;


bool match(std::string & user_id, std::string & banned_id){
    if (user_id.length() != banned_id.length()) return false;
    for (int i = 0; i < user_id.length(); ++i){
        if (banned_id[i] == '*') continue;
        if (user_id[i] != banned_id[i]) return false;
    }
    return true;
}


void dfs (std::vector<std::string> & user_id, 
          std::vector<std::string> & banned_id, 
          int banned_idx, std::vector<std::string> & res) {
    
    if (banned_idx == banned_id.size()){
        
        std::string str = "";
        std::vector<std::string> temp = res;
        std::sort(temp.begin(), temp.end()); // 주의 dfs 탐색에 영향을 줄 수 있음
        
        for (std::string s : temp){
            str += s;
        }
        
        if (only.find(str) == only.end()){
            ++answer;          
            only.insert(str);
        }
        return;
    }
    
    std::string target = banned_id[banned_idx];
    
    for (int i = 0; i < user_id.size(); ++i){
        if (used[i]) continue;
        if (match(user_id[i], target)){
            res.push_back(user_id[i]);
            used[i] = true;
            dfs(user_id, banned_id, banned_idx + 1, res);
            used[i] = false;
            res.pop_back();
        }
    }
}


int solution(std::vector<std::string> user_id, 
             std::vector<std::string> banned_id) 
{
    std::vector<std::string> res;
    dfs(user_id, banned_id, 0, res);
    return answer;
}