[2019 카카오 개발자 겨울 인턴십 코딩테스트] 문제3. 불량 사용자

문제풀이

 

범위가 작아 완탐이 가능한 문제입니다.

dfs를 사용하였고

문제에 

제재 아이디 목록들을 구했을 때 아이디들이 나열된 순서와 관계없이 아이디 목록의 내용이 동일하다면 같은 것으로 처리하여 하나로 세면 됩니다.

라는 부분을 보고 중복방지와 순서가 필요없다는 부분에서 set이 생각나 set을 사용하였습니다. 아이디 목록도 set

그 목록자체의 목록도 set으로 구성하여 이중 set을 사용하였습니다.

소스코드

#include <string>
#include <vector>
#include <set>
 
using namespace std;
 
int cnt = 0;
set<set<string>> comp;
 
bool compareCheck(string s1, string s2) {
    if (s1.length() != s2.length()) //길이비교
        return false;
    for (int i = 0; i < s1.length(); i++) {
        if (s1[i] == s2[i] || s2[i] == '*')
            continue;
        else {
            return false;
        }
    }
    return true;
}
 
void dfs(int idx, set<string> check_set, vector<vector<string>> candidate_list) {
    if (idx == candidate_list.size()) {
        if (check_set.size() == candidate_list.size()) {
            for (auto iter = comp.begin(); iter != comp.end(); iter++) {
                if (*iter == check_set)
                    return;
            }
            cnt++;
            comp.insert(check_set);
        }
        return;
    }
 
    for (int i = 0; i < candidate_list[idx].size(); i++) {
        if (check_set.find(candidate_list[idx][i]) == check_set.end()) {
            check_set.insert(candidate_list[idx][i]);
            dfs(idx + 1, check_set, candidate_list);
            check_set.erase(check_set.find(candidate_list[idx][i]));
        }
    }
}
 
int solution(vector<string> user_id, vector<string> banned_id) {
 
    vector<vector<string>> candidate_list;
 
    for (int i = 0; i < banned_id.size(); i++) {
        vector<string> temp;
        for (int j = 0; j < user_id.size(); j++) {
            if (compareCheck(user_id[j], banned_id[i])) {
                temp.push_back(user_id[j]);
            }
 
        }
        candidate_list.push_back(temp);
    }
    set<string> chk;
    dfs(0, chk, candidate_list);
 
    return cnt;
}

 

문제링크 : https://programmers.co.kr/learn/courses/30/lessons/64064

프로그래머스