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

해설

banned_id 의 각 패턴에 일치하는 user_id 를 고르는 경우의 수를 구하는 문제이다.

백트래킹 기법으로 banned_id[0], banned_id[1] .... banned_id[k-1] 에 일치하는 user_id[i]를 선택해 나가면 된다.

 

banned_id[k] 에 해당하는 user_id[i]를 선택할 때는, 

1) user_id[i]가 banned_id[0] ~ banned_id[k-1] 를 고르는 과정에서 선택되지 않았어야 하고

2) user_id[i] 가 banned_id[k] 패턴과 일치해야 한다.

 

조건을 만족하는 user_id[i]를 선택한 후 k개의 선택된 user_id를 기록해놓는다.

문제에서 아이디 목록의 내용이 동일한 경우는 하나로 세면 된다고 했으므로, k번까지 선택한 user_id의 모음을 정렬하여 set에 저장한다.

최종적으로, set의 size()를 리턴하면 정답이다.

 

 

코드

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <tuple>
#include <vector>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <iostream>

using namespace std;
using ii = pair<int, int>;
using iii = tuple<int, int, int>;

#define X first
#define Y second

string tmp;
set<string> sset;
vector<bool> visited(100, false);

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

void func(int k, const vector<string>& user_id, const vector<string>& banned_id) {
    
    if (k >= (int)banned_id.size()) {
        string s = tmp;
        sort(s.begin(), s.end());
        sset.insert(s);
        return ;
    }
    
    for (int i=0; i<(int)user_id.size(); i++) {
        if (visited[i]) continue;
        if (!check(user_id[i], banned_id[k])) continue;
        visited[i] = true;
        tmp += i+'0';
        func(k+1, user_id, banned_id);
        visited[i] = false;
        tmp.pop_back();
    }
}

int solution(vector<string> user_id, vector<string> banned_id) {
    
    func(0, user_id, banned_id);    
    return sset.size();
}