[프로그래머스] 불량 사용자

[프로그래머스] 불량 사용자

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

풀이 1

• 비트마스크 이용 풀이

#include <string>
#include <vector>
#include <set>
#include <iostream>

using namespace std;

set<int> ans; 
vector<string> user_id_g;
vector<string> banned_id_g;

//비트 마스크 집합에 포함된 원소의 개수 카운트
int bitCount(int x) {
	if (x == 0) return 0;
	return (x % 2) + bitCount(x / 2);
}

//응모자 아이디와 제재 아이디 매칭 가능한지 확인
bool match(string a, string b) {
	if (a.length() != b.length()) return false;

	for (int i = 0; i < a.length(); ++i) {
		if (a[i] == '*' || b[i] == '*') continue;
		if (a[i] != b[i]) return false;
	}
	return true;
}

//banned_index번째 제재 아이디와 매칭 가능한 응모 아이디가 있는지 확인한다
//bitmask는 현재까지 제재 아이디와 매칭한 응모 아이디를 기록한다
//하나의 제재 아이디 당 하나의 응모 아이디가 매칭되도록 한다
void dp(int banned_index, int bitmask) {
	//제재 아이디 목록의 끝까지 확인한 경우
	if (banned_id_g.size() == banned_index) {
    	//매칭된 응모 아이디의 개수가 제재 아이디의 개수와 같은지 확인한다
		if (bitCount(bitmask) == banned_id_g.size()) {
        	//모든 제재 아이디가 각각 하나의 응모 아이디와 중복되지 않게 매칭 성공
			//bitmask 결과가 중복되어 세어지지 않도록 집합에 저장
			ans.insert(bitmask);
		}
		return;
	}
	
    //전체 응모 아이디를 순회하며 banned_index번째 제재 아이디와 매칭 가능한지 확인
	for (int i = 0; i < user_id_g.size(); ++i) {
		if (match(user_id_g[i], banned_id_g[banned_index])) {
        	//bitmask 집합에 포함되었다면, 이미 다른 제재 아이디와 매칭된 것이므로
            //bitmask 집합에 포함되지 않은 응모 아이디인지 확인한다
			if ((bitmask & (1 << i)) == 0) {
            	//응모 아이디가 매칭되었음을 bitmask에 기록하고 다음 banned_index로 이동
				dp(banned_index + 1, bitmask | (1 << i));
			}
		}
	}
}

int solution(vector<string> user_id, vector<string> banned_id) {
	//전역 변수로 사용하기 위해 매개변수로 받은 벡터를 복사한다
	user_id_g = user_id;
	banned_id_g = banned_id;

	int answer = 0;
	
    //0번째 제재 아이디부터 검사, 매칭된 응모 아이디가 없으므로 bitmask = 0인 상태로 호출
	dp(0, 0);
	answer = ans.size();

	return answer;
}

풀이 2

• 비트마스크 없이 다중 for문 이용 풀이

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

using namespace std;

bool isPossible(string u_id, string b_id){
    if(u_id.length() != b_id.length()) return false;
    
    for(int i = 0; i<b_id.length(); ++i){
        if(b_id[i] == '*') continue;
        if(b_id[i] != u_id[i]) return false;
    }
    return true;
}

int solution(vector<string> user_id, vector<string> banned_id) {
    int n = user_id.size();
    int m = banned_id.size();
    
    vector<vector<string>> possible_banned_id(m);
    for(int i = 0; i<m; ++i){
        string b_id = banned_id[i];
        for(int j = 0; j<n; ++j){
            string u_id = user_id[j];
            
            if(isPossible(u_id, b_id)) possible_banned_id[i].push_back(u_id);
        }
    }
    for(int i = 0; i<m; ++i){
        if(possible_banned_id[i].empty()) return 0;
        
        // for(int j = 0; j<possible_banned_id[i].size(); ++j){
        //     cout << possible_banned_id[i][j]<<" ";
        // }
        // cout << "\n";
    }
    
    set<set<string>> answerSet;
    set<string> possible_answer;
    for(int a = 0; a< possible_banned_id[0].size(); ++a){
        string stra = possible_banned_id[0][a];
        possible_answer.insert(stra);
        if(m == 1){
            answerSet.insert(possible_answer);
            possible_answer.erase(stra);
            continue;
        }
        for(int b = 0; b < possible_banned_id[1].size(); ++b){
            string strb = possible_banned_id[1][b];
            if(possible_answer.find(strb) != possible_answer.end()) continue;
            possible_answer.insert(strb);
            if(m == 2){
                answerSet.insert(possible_answer);
                possible_answer.erase(strb);
                continue;
            }
            for(int c = 0; c < possible_banned_id[2].size(); ++c){
                string strc = possible_banned_id[2][c];
                if(possible_answer.find(strc) != possible_answer.end()) continue;
                possible_answer.insert(strc);
                if(m == 3){
                    answerSet.insert(possible_answer);
                    possible_answer.erase(strc);
                    continue;
                }
                for(int d = 0; d < possible_banned_id[3].size(); ++d){
                    string strd = possible_banned_id[3][d];
                    if(possible_answer.find(strd) != possible_answer.end()) continue;
                    possible_answer.insert(strd);
                    if(m == 4){
                        answerSet.insert(possible_answer);
                        possible_answer.erase(strd);
                        continue;
                    }
                    for(int e = 0; e < possible_banned_id[4].size(); ++e){
                         string stre = possible_banned_id[4][e];
                        if(possible_answer.find(stre) != possible_answer.end()) continue;
                        possible_answer.insert(stre);
                        if(m == 5){
                            answerSet.insert(possible_answer);
                            possible_answer.erase(stre);
                            continue;
                        }
                        for(int f = 0; f < possible_banned_id[5].size(); ++f){
                            string strf = possible_banned_id[5][f];
                            if(possible_answer.find(strf) != possible_answer.end()) continue;
                            possible_answer.insert(strf);
                            if(m == 6){
                                answerSet.insert(possible_answer);
                                possible_answer.erase(strf);
                                continue;
                            }
                            for(int g = 0; g < possible_banned_id[6].size(); ++g){
                                string strg = possible_banned_id[6][g];
                                if(possible_answer.find(strg) != possible_answer.end()) continue;
                                possible_answer.insert(strg);
                                if(m == 7){
                                    answerSet.insert(possible_answer);
                                    possible_answer.erase(strg);
                                    continue;
                                }
                                for(int h = 0; h < possible_banned_id[7].size(); ++h){
                                    string strh = possible_banned_id[7][h];
                                    if(possible_answer.find(strh) != possible_answer.end()) continue;
                                    possible_answer.insert(strh);
                                    
                                    answerSet.insert(possible_answer);
                                    possible_answer.erase(strh);
                                }
                                possible_answer.erase(strg);
                            }
                            possible_answer.erase(strf);
                        }
                        possible_answer.erase(stre);
                    }
                    possible_answer.erase(strd);
                }
                possible_answer.erase(strc);
            }
            possible_answer.erase(strb);
        }
        possible_answer.erase(stra);
    }
    
    for(auto it = answerSet.begin(); it != answerSet.end(); ++it){
        if(it->size() != m) answerSet.erase(it);
    }
    
    // for(auto it = answerSet.begin(); it != answerSet.end(); ++it){
    //     for(auto innerit = it->begin(); innerit != it->end(); ++innerit){
    //         cout << *innerit<<" ";
    //     }
    //     cout << "\n";
    // }
    
    int answer = answerSet.size();
    return answer;
}