[프로그래머스/Level 3] 불량 사용자 (C++)

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

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

카카오 인턴 기출

 

카카오 기출문제였던 순위검색처럼 banned_list와 매칭될 수 있는 user_id의 모든 경우의 수를 비트 연산을 이용해서 구하려고 시도했는데, 올바른 접근 방법이 아니었던 것 같습니다. 두 아이디의 길이, 그리고 *이 아니고 다른 문자가 같은지를 통해 해당 아이디가 불량 사용자의 후보가 될 수 있는지 확인하고, 이를 DFS를 통해 모든 경우의 수를 구합니다. 그리고 set과 정렬을 이용해, 중복되지 않게 조합을 추출합니다.

 

#include <string>
#include <vector>
#include <unordered_set>
#include <algorithm>
using namespace std;

vector<string> uid, bid;
unordered_set<vector<int> > bList;
bool visit[9];

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

void DFS(int cnt, vector<int> candidate) {
    if(idx == bid.size()) {
        sort(candidate.begin(), candidate.end());
        bList.insert(candidate);
        return;
    }
    
    for(int i = 0; i < uid.size(); i++) {
        if(!visit[i] && check(uid[i], bid[cnt])) {
            visit[i] = true;
            candidate.push_back(i);
            DFS(idx + 1, candidate);
            candidate.pop_back();
            visit[i] = false;
        }
    }
}

int solution(vector<string> user_id, vector<string> banned_id) {
    uid = user_id;
    bid = banned_id;
    vector<int> candidate;
    DFS(0, candidate);
    
    return bList.size();
}