불량 사용자

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

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

<JAVA>

import java.util.*;
import java.util.regex.Pattern; //정규식 사용하기 위한 라이브러리 추가
class Solution {
    
    
    ArrayList<ArrayList<String>>bidList = new ArrayList<>();
    HashSet<HashSet<String>> result = new HashSet<>();
    
    ArrayList<String> findbidList(String bid, String[] user_id){
        
        String pattern = bid.replace('*','.');
        ArrayList<String> arr = new ArrayList<>();
        for(String userId:user_id){
            if(Pattern.matches(pattern,userId)){ //비교기준, 비교대상 순으로
                arr.add(userId);
            }
        }
        return arr;
    }
    
    public void dfs(int depth,HashSet<String>hs ){
        
        if(depth==bidList.size()){
            result.add(new HashSet<>(hs));
            return;
        }
        
        for(int i=0; i<bidList.get(depth).size(); i++){
            String s = bidList.get(depth).get(i);
            if(!hs.contains(s)){ // 이미 포함한건지 안한건지 확인 (불량사용자 후보로 두번이상 지목될 수 있기 때문에)
                hs.add(s);
                dfs(depth+1,hs);
                hs.remove(s);
            }
        }
        
        
    }
    
     public int solution(String[] user_id, String[] banned_id) {
            
            for(String bannedId:banned_id){
                
                bidList.add(findbidList(bannedId,user_id));
                
            }
         
         dfs(0,new HashSet<>());
         return result.size();
    
     }
}

<불량사용자후보 추출하기>

- 정규식 사용 : Pattern.matches(pattern,userId); 

- 정규식을 사용하기 전에 '*'을 '.'으로 바꾼다: bid.replace('*','.');

<불량사용자의 경우의 수 구하기> 

- 불량사용자후보중 누굴 추출할 것인지 고를 때 dfs를 사용해야한다.

- 추출하는 과정에서 불량사용자 후보로 두번이상 지목 될 수 있기 때문에 이미 추출한 userId라면 포함하면 안됨

 

<C++>

#include <string>
#include <vector>
#include <iostream>
#include<set>
#include<map>
using namespace std;
int ans=0;

bool checkallstars(string bid){
    for(int i=0; i<bid.size(); i++){
        if(bid[i]!='*'){
            return false;
        }
    }
    return true;
}


void dfs(  vector<string>& banned_id, int count, set<string>s, map<string,vector<string>>&m, set<set<string>>&check ){
    
    if(count == banned_id.size()){
        if(check.find(s)==check.end()){
            check.insert(s);
            ans++;
        }
        return;
    }
  
    string bid = banned_id[count];
    
    vector<string>candidates = m[bid];

    for(int i=0; i<candidates.size(); i++){
        if(s.find(candidates[i])==s.end()){
            s.insert(candidates[i]);
            dfs(banned_id, count+1, s,m,check);
            s.erase(candidates[i]);
        }
    }
   
    return;

}

//각 banned_id에 해당하는 후보들을 구한다. -> 모든 경우의 수를 탐색한다. 

int solution(vector<string> user_id, vector<string> banned_id) {
    
    int answer = 0;
    map<string,vector<string>>m;
    set<set<string>> check; 
    set<string>s;
   
    for(int i=0; i<banned_id.size(); i++){
        string bid =banned_id[i];
        if(m.find(bid)==m.end()){
        if(checkallstars(bid)){
           for(int k=0; k<user_id.size(); k++){
               if(bid.size()==user_id[k].size()){
                 m[bid].push_back(user_id[k]);
               }
           }
            continue;
        }
        for(int j=0; j<user_id.size(); j++){
            string uid = user_id[j];
            bool ch = true;
            if(uid.size()!=bid.size()){continue;}
            for(int t=0; t<bid.size(); t++){
                if(bid[t]=='*'){continue;}
                if(bid[t]!=uid[t]){ch=false; break;}
            }
            if(ch==true){
            
                m[bid].push_back(uid);
            }
        }
     }
    }
    
    dfs(banned_id,0,s,m,check);
    answer =ans;
    return answer;
}

- banned_id 배열의 값을 key 값으로 하는 맵을 통해 후보들을 저장하고 dfs로 탐색하면서 불량 사용자 리스트의 종류를 모두 구한다.