프로그래머스 - 불량 사용자

프로그래머스 - 불량 사용자

주어지는 크기가 최대 20개 정도라 user_id에서 banned_id 갯수만큼 조합을 다 구한 뒤 일일히 비교해가면서 해도 충분히 가능한 문제이다.

핵심은 banned_id와 user_id에서 banned_id 갯수만큼 뽑은 조합이 매핑이 가능한지를 체크해야하는데, 이것이 Greedy하게 가능하다는 점이다.
예를 들어,
user_id : ["frodo", "fradi", "crodo", "abc123", "frodoc"]
banned_id : ["fr*d*", "abc1**"] 일 때,
"fr*d*"에 해당하는 것은 "frodo", "fradi"가 존재하고, "abc1**"에 해당되는 것은 "abc123"이 존재하기 때문에, frodo, abc123 혹은 fradi, abc123이 조합되는 경우에 정답이 가능해서 답은 2가 된다.

문제는 다음의 경우이다.
user_id : ["frodo", "fradi", "crodo", "abc123", "frodoc"]
banned_id : ["fr*d*", "*rodo", "******", "******"]
문제에선 1개의 user_id가 만약 특정 banned_id에 매핑될 경우 다시 사용되지 않기 때문에, 만약 ["frodo", "fradi", "abc123", "frodoc"]가 조합으로 선택된 경우 fr*d에 frodo가 매핑된다면 *rodo에 매핑될 user_id가 없기 때문에 마치 불가능한 경우처럼 취급될 수 있다.
하지만 frodo를 *rodo에 매핑하고, fradi를 fr*d에 매핑한다면 위 케이스는 가능한 케이스이다.

이를 방지하기 위해서 banned_id를 기준으로 가능한 user_id 원소 갯수를 카운트한 뒤, 이들을 오름차순으로 정렬한 뒤, Greedy하게 선택하다도록 했다. (코드의 48~58번째 라인)

예를 들어 위 케이스 같은 경우 fr*d에 매핑이 가능한 user_id는 2개이고, *rodo에 매핑이 가능한 user_id는 1개이기 떄문에, *rodo가 먼저 frodo에 매핑되도록 한다. 그 후에 fr*d에 fradi가 매핑되도록하면 된다.
즉, banned_id를 기준으로 매핑이 가능한 user_id 갯수가 적은 것부터 Greedy하게 선택해주면 user_id와 banned_id를 합쳐서 모든 조합을 구하지 않아도 문제를 풀 수 있다.

코드는 아래와 같다.

#include <string>
#include <vector>
#include <algorithm>
#include <cstring>

using namespace std;

int answer;
int user_id_size;
int banned_id_size;
int candidate[128];
int visit[128];
vector<string> user_id_list;
vector<string> banned_id_list;
int banned_id_cnt[128];

bool comp(const vector<int> &a, const vector<int> &b)
{
    return a.size() < b.size();
}
void comb(int n, int depth)
{
    if(depth == n) {
        int banned_id_checked[n];
        memset(banned_id_checked, 0, sizeof(banned_id_checked));
        vector<string> candi;
        vector<vector<int>> candi_list(n);
        for(int i=0;i<n;i++) 
            candi.push_back(user_id_list[candidate[i]]);
        
        for(int i=0;i<n;i++) {
            for(int j=0;j<n;j++) {
                if(banned_id_list[i].size() != candi[j].size())
                    continue;
                int cnt = 0;
                for(int k=0;k<candi[j].size();k++) {
                    if(banned_id_list[i][k] == '*')
                        continue;
                    if(banned_id_list[i][k] != candi[j][k])
                        break;
                    cnt++;
                }
                if(cnt == banned_id_cnt[i]) 
                    candi_list[i].push_back(j);
            }
        }
        
        sort(candi_list.begin(), candi_list.end(), comp);
        int match = 0;
        int user_id_checked[n];
        memset(user_id_checked, 0, sizeof(user_id_checked));
        for(int i=0;i<n;i++) 
            for(int j=0;j<candi_list[i].size();j++) 
                if(user_id_checked[candi_list[i][j]] == 0) {
                    user_id_checked[candi_list[i][j]] = 1;
                    match++;
                    break;
                }
        
        if(match == n) 
            answer++;
        
        return;
    }
    
    for(int i=0;i<user_id_size;i++) {
        if(visit[i])
            continue;
        if(depth > 0 && candidate[depth - 1] >= i)
            continue;
        visit[i] = 1;
        candidate[depth] = i;
        comb(n, depth + 1);
        visit[i] = 0;
    }
}
int solution(vector<string> user_id, vector<string> banned_id) {
    answer = 0;
    user_id_size = user_id.size();
    user_id_list = user_id;
    banned_id_size = banned_id.size();
    banned_id_list = banned_id;
    for(int i=0;i<banned_id_size;i++) {
        banned_id_cnt[i] = 0;
        for(int j=0;j<banned_id[i].size();j++) 
            if(banned_id[i][j] != '*')
                banned_id_cnt[i]++;
    }
    for(int i=0;i<128;i++)
        visit[i] = 0;
    
    comb(banned_id_size, 0);
    
    return answer;
}