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

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

풀이

완전탐색을 해서 가능한 경우를 모두 확인해주었다. set을 통해서 중복되는 경우를 걸러주었다.

코드

#include <string>
#include <vector>
#include<set>
using namespace std;

bool visited[10];
set<string> ans;

void dfs(vector<string>& user_id, vector<string>& banned_id, int idx) {
    if (idx == banned_id.size()) {
        //  set으로 중복 체크
        string res = "";
        for (int i = 0; i < user_id.size(); i++) {
            if (visited[i]) {
                res += i;
            }
        }
        ans.insert(res);
        return;
    }

    for (int i = 0; i < user_id.size(); i++) {
        // 길이가 다르거나 이미 불량사용자에 매핑된 경우 제외
        if (banned_id[idx].size() != user_id[i].size() || visited[i])  continue;

        bool find = true;
        for (int j = 0; j < user_id[i].size(); j++) {
            if (banned_id[idx][j] == '*') continue;
            if (banned_id[idx][j] != user_id[i][j]) {
                find = false;
                break;
            }
        }

        // 불량 사용자를 찾은 경우
        if (find) {
            visited[i] = true;
            dfs(user_id, banned_id, idx + 1);
            visited[i] = false;
        }
    }
}
int solution(vector<string> user_id, vector<string> banned_id) {
    dfs(user_id, banned_id, 0);
    int answer = ans.size();
    return answer;
}