코딩테스트 : 불량 사용자

문제 설명

해당 문제는 불량 사용자 목록(banned_id)에 와일드카드(*)가 포함되어 있으며, 이 와일드카드에 매칭되는 사용자 ID(user_id)를 조합하여 가능한 제재 아이디 목록의 경우의 수를 구하는 문제다.

 

 

핵심 방법

banned_id의 각 패턴에 대해 user_id에서 매칭 가능한 인덱스를 미리 구해둔다.

BFS를 활용해 각 banned_id에 user_id를 하나씩 매핑하면서 중복되지 않도록 제재 아이디 조합을 만든다.

각 조합은 set<int> 형태로 저장하고, set<set<int>>으로 중복 조합을 제거해 경우의 수를 센다.

 

BFS에 대한 자세한 내용은 아래 블로그에서 확인할 수 있다.

BFS(Breadth-First-Search) 넓이 우선 탐색

set에 대한 자세한 내용은 아래 블로그에서 확인할 수 있다.

 

중복을 방지해주는 자료구조 Set

 

int bfs(vector<vector<int>> banList)
{
    queue<pair<set<int>, int>> q; // <현재까지 선택된 user_id 인덱스 조합, banned_id 진행 인덱스>
    set<int> s; 
    q.push({s, 0}); // 초기 상태 (아무것도 선택 안함, 0번째 banned_id부터 시작)

    while(!q.empty())
    {
        pair<set<int>, int> current = q.front();
        int index = current.second;

        if(index == banList.size()) // 모든 banned_id를 다 매핑했으면 break
            break;

        q.pop();

        for(int i : banList[index]) // 현재 banned_id에 대해 매칭 가능한 user_id 인덱스를 순회
        {
            set<int> temp = current.first; 
            temp.insert(i); // user_id 인덱스를 넣음

            if(current.first.size() == temp.size()) // 이미 들어있던 user_id면 continue
                continue;

            q.push({temp, index + 1}); // 다음 banned_id로 넘어감
        }
    }

    set<set<int>> sv; // 중복 제거를 위한 set의 set
    while(!q.empty())
    {
        pair<set<int>, int> temp = q.front();
        sv.insert(temp.first); // 제재 아이디 조합을 저장
        q.pop();
    }

    return sv.size(); // 가능한 조합의 수 반환
}

bool checkBan(string str1, string str2)
{
    if(str1.size() != str2.size())
        return false;

    for(int i = 0; i < str1.size(); i++)
    {
        if(str2[i] == '*') // 와일드카드는 비교 생략
            continue;
        if(str1[i] != str2[i]) // 다른 글자면 false
            return false;
    }
    return true; // 모두 일치하거나 와일드카드
}

int solution(vector<string> user_id, vector<string> banned_id) {
    vector<vector<int>> v(banned_id.size(), vector<int>());

    // 각 banned_id에 대해 매칭되는 user_id 인덱스 저장
    for(int i = 0; i < banned_id.size(); i++)
    {
        for(int j = 0; j < user_id.size(); j++)
        {
            if(checkBan(user_id[j], banned_id[i]))
            {
                v[i].push_back(j); // banned_id[i]와 매칭되는 user_id[j]의 인덱스 추가
            }
        }
    }

    return bfs(v); // 가능한 조합의 수 계산
}