Level 3. 불량 사용자

Level 3. 불량 사용자

 

 

우선 banned_id의 각 패턴과 일치하는 후보들을 정규 표현식을 활용해 저장했다.

• 한 단어는 '.' 문자에 해당한다.
• regex_match() 함수는 전체 문자열에 대한 검사이고, regex_search() 함수는 부분 문자열에 대한 검사이다.

 

그리고는 DFS를 이용해 조합을 구했다.

 

중복을 제거하기 위해 set<set<string>> 자료형을 사용했는데, 안쪽의 set은 하나의 경우에서 중복을 방지하기 위함이고, 바깥쪽의 set은 다른 경우 간 중복을 방지하기 위함이다.

• unordered_set<set<string>> 자료형을 써도 되지만, 컴파일 오류로 실행되지 않았다.

 

#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
#include <regex>

using namespace std;

void rDFS(vector<vector<string>>& candidates, set<string> current, set<set<string>>& result)
{
    if (candidates.size() <= current.size())
    {
        result.emplace(current);
        return;
    }

    for (string& s : candidates[current.size()])
    {
        if (current.find(s) != current.end())
            continue;

        set<string> st(current);
        st.emplace(s);

        rDFS(candidates, st, result);
    }
}

int solution(vector<string> user_id, vector<string> banned_id)
{
    vector<vector<string>> candidates;

    for (string& bnid : banned_id)
    {
        replace(bnid.begin(), bnid.end(), '*', '.');

        candidates.resize(candidates.size() + 1);

        for (string& usid : user_id)
            if (regex_match(usid, regex(bnid)))
                candidates.back().emplace_back(usid);
    }

    set<set<string>> result;

    rDFS(candidates, {}, result);

    return result.size();
}