2019카카오 인턴쉽 - 불량 사용자

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

프로그래머스

• 금지된 아이디가될 가능성이 있는 user_id를 찾아서 vector를 만든다
• 만들어 놓은 vector를 재귀함수와 비트마스크를 이용하여 중복되지 않게 만든다

---

중요 개념

1001 | 0110 -> 1111

1001 & 0110 -> 0000

 

1<<3  -> 1000   1을 왼쪽으로 3만큼 이동

1000>>3  -> 1   1을 오른쪽으로 3만큼 이동

bool visited[1 << 8]  ->  배열크기가 2^8이다. 왜? 1을 8만큼 이동하고 10진법으로 바꿨기 때문.

비트마스크 관련 링크

https://mygumi.tistory.com/361

비트마스크(BitMask) 는 무엇인가? :: 마이구미

 

#include<iostream>
#include <string>
#include <vector>
using namespace std;
bool visited[1 << 8];
void dfs(int bannedIdx, int N,int bit ,const vector<vector<int>>& candi)
{
    if (N == bannedIdx)
    {
        visited[bit] = true;
        return;
    }
    for (auto p : candi[bannedIdx]) {
        if (bit & (1 << p)) continue;
        dfs(bannedIdx+1, N, bit|(1<<p), candi);
    }
}

bool check(string b, string u) {
    if (b.size() != u.size()) return false;
    for (int i = 0; i < b.size(); i++) {
        if (!(b[i] == u[i] || b[i] == '*' || u[i] == '*')) {
            return false;
        }
    }
    return true;
}

int solution(vector<string> user_id, vector<string> banned_id) {
    int answer = 0;
    vector<vector<int>> candi(banned_id.size());
    for (int i = 0; i < banned_id.size(); i++) {
        for (int j = 0; j < user_id.size(); j++) {
            if (check(banned_id[i], user_id[j])) {
                candi[i].push_back(j);
            }
        }
    }
    dfs(0, banned_id.size(),0 ,candi);
    for (int i = 0; i < (1 << 8); i++) {
        if (visited[i])
            answer++;
    }
    return answer;
}

int main() {
    vector<string> user_id = { "frodo", "fradi", "crodo", "abc123", "frodoc" };
    vector<string> banned_id = { "fr*d*", "*rodo", "******", "******" };
    cout<<solution(user_id, banned_id);
}