[프로그래머스 2019 카카오 개발자 겨울 인턴십] 불량 사용자

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

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

처음에 매우 어렵게 접근했다.

하지만 문제에서 구하고자 하는 바가 불량 아이디 케이스 별 집합 이라는 것을 알면 접근이 쉬워진다.

 

유저 아이디에서 불량 아이디를 체크하여 그 경우의 수를 집합에 담는다.

{1,3,4} 나 {3,4,1}이나 같은 케이스로 취급하기 때문

 

유저아이디도 최대 8개이기 때문에 dfs를 돌려서 모두 확인하는 방법이 최선이다.

 

dfs(parameter: 현재 체크할 불량 아이디 인덱스)

종료 조건: 체크한 불량 아이디 수 == 불량 아이디 전체 수

 

for:

현재 체크할 불량 아이디에 대해 모든 유저 아이디를 체크

if 이미 체크된 아이디 then continue;

else 

 아이디 불량 여부 체크

  if 불량 then

     불량 체크

     다음 dfs로

     불량 체크 해제

 

요런 식이다. 현재 체크한 불량 아이디는 visitied배열로 확인한다.

#include <string>
#include <vector>
#include <set>

using namespace std;

set<int> s;
int visited[8];
int blen;
void DFS(int bidx, vector<string> &user_id, vector<string> &banned_id){
    if(bidx == blen){
        int tmp = 0;
        for(int i=0; i<user_id.size(); i++){
            if(visited[i]){
                tmp = tmp| 1<<i;
            }
        }
        s.insert(tmp);
        return;
    }
    
    string banned = banned_id[bidx];
    for(int i=0; i<user_id.size(); i++){
        if(visited[i]) continue;
        
        string user = user_id[i];
        
        if(user.length() != banned.length()){
            continue;
        }
        
        // 일치 여부 비교
        bool flag = true;
        for(int j=0; j<banned.size(); j++){
            if(banned[j] == '*') continue;
            
            if(banned[j] != user[j]){
                flag = false;
                break;
            }
        }
        
        if(flag){
            visited[i] = 1;
            DFS(bidx+1, user_id, banned_id);
            visited[i] = 0;
        }
    }
}
int solution(vector<string> user_id, vector<string> banned_id) {
    int answer = 0;
    blen = banned_id.size();
    DFS(0, user_id, banned_id);
    answer = s.size();
    return answer;
}