[프로그래머스 Level_3 / C++ / 카카오] 불량 사용자

dfs와 비트연산자를 사용해서 풀면된다. 

 

#접근방법

 

user_id 의 사이즈만큼 반복문을 돌리면서 banned_id를 차례대로 

비교해가면서 문자열이 성립될 때  dfs를 호출한다. 

 

이때, 방문을 표현하는 v 라는 변수에 v|(1<<i) 라는 값을 매개변수로 전달한다.

 

예를 들어,

v 값이 5라고 가정하자.

해당 값을 이진수로 표현하면 

 

"101" (1은 방문을 표시)

 

즉, user_id 에서 인덱스 0번과 2번을 방문했다는 뜻이다.

 

이 값에서 1<<i ( i가 3이라면 )

 

1000 로 표현 되는데 이때 

 

v|(1<<i) 를 하면 1101 이 된다. 

 

즉, 현재 3번째 user_id 와 banned_id가 성립이 되었으므로 

방문 처리를 해주면서 dfs를 호출한다. 

 

재귀 호출을 반복하다가 cnt값이 banned_id의 사이즈가 되었을 때

현재 방문 된 값을 인덱스로 가지는 배열에 체크를 해주며

result 값을 증가시켜준다. 

 

이후에 방문한 순서는 다르지만 방문한 결과값이 

같은 경우는 무시한다. 

 

#include <string>
#include <vector>
#include <iostream>
using namespace std;
vector <string> uid, bid;
int visited[1<<8], result; 
void dfs(int idx, int cnt, int v){
    if(cnt==bid.size()){
        if(!visited[v]){
            visited[v]=1; 
            result++; 
        }
        return ; 
    }    
    for(int i=0; i<uid.size(); i++){
           if(v&(1<<i))continue; 
           int k, j=idx;     
            if(uid[i].size()!=bid[j].size())continue; 
            for(k=0; k<bid[j].size(); k++){
                if(bid[j][k]!='*'&&bid[j][k]!=uid[i][k])break; 
            }
            if(k==bid[j].size()) dfs(idx+1, cnt+1, v|(1<<i));                  
    }    
}

int solution(vector<string> user_id, vector<string> banned_id) {
    int answer = 0;
    uid=user_id; 
    bid=banned_id;
    dfs(0, 0, 0);
    answer=result;     
    return answer;
}

 

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