[programmers] Lv.3 불량 사용자(c++)

#include <string>
#include <vector>
#include <regex>
#include <set>

using namespace std;

set<set<string>> answer;
void find_all(vector<vector<string>>& ban_possible, set<string> banned = {}, int i=0){
    for(auto possible: ban_possible[i]){
        if(banned.find(possible) != banned.end()) continue;
        else banned.insert(possible);

        if(i+1 != ban_possible.size()) find_all(ban_possible, banned, i+1);
        if(i+1 == ban_possible.size() && banned.size() == ban_possible.size()) {
            answer.insert(banned);
        }
        banned.erase(possible);
    }
}


int solution(vector<string> user_id, vector<string> banned_id) {
    vector<vector<string>> ban_possible;
    for(string& id: banned_id){
        string reg="";
        for(char& ch: id){
            if(ch=='*') reg+="[\\da-z]";
            else reg+=ch;
        }
        smatch match;
        vector<string> possible;
        for(string id: user_id){            
            regex_match(id, match, regex(reg));
            if(match.str().size()!=0) {
                possible.push_back(match.str());
            }
        }
        ban_possible.push_back(possible);
    }
    
    find_all(ban_possible);
    return answer.size();
}

---

문제

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

코딩테스트 연습 - 불량 사용자

728x90

---

[접근1]

regex_match를 사용하여 불량사용자에 해당되는 아이디를 찾아낼것이다.

이를 위해서 불량 사용자 아이디 string을 정규표현식 형태로 바꿔준다.

각 *마다 [\\da-z]를 넣어줬다. 즉 숫자 아니면 소문자라는 의미.

각 제재 아이디를 ban_possible에 넣어줬다.

vector<vector<string>> ban_possible;
for(string& id: banned_id){
    string reg="";
    for(char& ch: id){
        if(ch=='*') reg+="[\\da-z]";
        else reg+=ch;
    }
    smatch match;
    vector<string> possible;
    for(string id: user_id){            
        regex_match(id, match, regex(reg));
        if(match.str().size()!=0) {
            possible.push_back(match.str());
        }
    }
    ban_possible.push_back(possible);
}

---

[접근2]

각 불량 사용자의 제재 아이디를 돌면서 하나씩 뽑아서 set에 넣어준다.

set에 동일한 아이디가 있으면 다음 제재 아이디를 확인하기 위해 돌아간다.

아직 불량 사용자 목록이 남았다면 find_all 함수를 한번 더 실행해주고,

모든 불량 사용자 목록을 돌았을 때 set에 남아있는 id의 수가 불량 사용자 수와 같다면 answer set에 넣어준다.

set이기 때문에 동일한 목록이 중복되지 않는다.

banned set에 담겨있는 id를 제거해준 뒤 다음 제재 아이디를 확인하기 위해 for문으로 돌아간다.

answer의 크기가 곧 답이다.

set<set<string>> answer;
void find_all(vector<vector<string>>& ban_possible, set<string> banned = {}, int i=0){
    for(auto possible: ban_possible[i]){
        if(banned.find(possible) != banned.end()) continue;
        else banned.insert(possible);

        if(i+1 != ban_possible.size()) find_all(ban_possible, banned, i+1);
        if(i+1 == ban_possible.size() && banned.size() == ban_possible.size()) {
            answer.insert(banned);
        }
        banned.erase(possible);
    }
}