(C++) - 프로그래머스(2019 카카오 개발자 겨울 인턴십) : 불량 사용자

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

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

dfs 구현 문제였습니다.

 

풀이방법

 1. 하나의 banned_id에 해당하는 user_id들을 index로 뽑아 저장합니다. 예제2의 경우 "*rodo" 에 해당하는 [0,2] index를 저장해줍니다. 마찬가지로 나머지 "*rodo", "******"에 대해 [0,2], [3,4]를 저장해줍니다.

 

 2. 목록을 dfs로 뽑아준 후 map에 저장해줍니다. [0,2,3], [0,2,4]를 뽑아야 하므로 자기 자신을 제외하고 뽑았던 것을 뽑지 않도록 적절히 구현해줍니다.

 

 3. map.size()를 반환해줍니다.

 

Code

#include <bits/stdc++.h>

using namespace std;
vector <int> a;
map<string,int> m;
int ck[10];
void dfs(int depth, int idx, vector<vector<int>> caseArr){
    if(depth == caseArr.size()){
        string ans ="";
        for(auto el:a) ans += to_string(el);
        sort(ans.begin(),ans.end());
        m[ans] = 1;
        return ;
    }
    for(int i = 0; i < caseArr[idx].size(); i++){
        if(ck[caseArr[idx][i]]) continue;
        a.push_back(caseArr[idx][i]);
        ck[caseArr[idx][i]] = 1;
        dfs(depth+1,idx+1,caseArr);
        ck[caseArr[idx][i]] = 0;
        a.pop_back();
    }
}

int solution(vector<string> user_id, vector<string> banned_id) {
    int answer = 0;
    a.clear();
    m.clear();
    memset(ck,0,sizeof(ck));
    vector <vector<int>> caseArr;

    for(int i = 0; i < banned_id.size(); i++){
        int cnt = 0;
        vector<int>comb;
        for(int j = 0; j < user_id.size(); j++){
            if(banned_id[i].size()!=user_id[j].size()) continue;
            int matchFlag = 1;
            for(int k = 0; k < banned_id[i].size(); k++){
                if(banned_id[i][k] == '*') continue;
                if(banned_id[i][k]!=user_id[j][k]) {
                    matchFlag = 0;
                    break;
                }
            }
            if(matchFlag) {
                comb.push_back(j);
            }
        }

        caseArr.push_back(comb);
        comb.clear();
    }

    dfs(0,0,caseArr);

    return m.size();
}