[프로그래머스] 불량 사용자(C++)

[문제]

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

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

[풀이]

 

각각의 banned_id마다 가능한 user_id의 index를 vector에 push

DFS를 통해 banned_id마다 제재 id를 구한다.

banned_id에 대해 user ID를 모두 선택했을 경우, 선택된 user ID의 index로 문자열을 만들어 set에 insert해준다.

set을 통해 중복된 경우를 제거하여 모든 경우의 수를 구할 수 있다.

 

[코드]

 

#include <string>
#include <vector>
#include <set>
#define MAX 8

using namespace std;

vector<int> v[MAX];
set<string> s;
bool visited[MAX]={0,};
int bsize= 0;
int usize=0;
int res= 0;

void DFS(int cnt,int idx)
{
    if(cnt == bsize)
    {
        string tmp="";
        for(int i=0;i<usize;i++){
            if(visited[i])  tmp+=to_string(i);
        }
        s.insert(tmp);
        return ;
    }
    for(int i=0;i<v[idx].size();i++)
    {
        int num = v[idx][i];
        if(visited[num])    continue;
        visited[num]=true;
        DFS(cnt+1, idx+1);
        visited[num] = false;
    }
}

int solution(vector<string> user_id, vector<string> banned_id) {
    int answer = 0;
    bsize= banned_id.size();
    usize= user_id.size();
    for(int i=0;i<bsize;i++)
    {
        int len1= banned_id[i].size();
        for(int j=0;j<user_id.size();j++)
        {
            int len2 = user_id[j].size();
            if(len1 != len2)    continue;
            bool check = true;
            for(int k=0;k<len1;k++){
                if(banned_id[i][k] == '*')  continue;
                if(banned_id[i][k] != user_id[j][k]){
                    check = false;
                    break;
                }
            }
            if(check)   v[i].push_back(j);            
        }   
    }

    DFS(0,0);
    answer = s.size();
    return answer;
}