Programmers 불량 사용자

programmers 불량 사용자 : programmers.co.kr/learn/courses/30/lessons/64064

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

2019 카카오 개발자 겨울 인턴십에 나온 불량 사용자 입니다.

dfs(backtraking)의 대표적인 문제입니다.

 

현재 어떤 userId가 banId될 수 있는지 유지하면서 dfs로 모든 userId를 banId와 비교하였습니다.

중요한 것은 답이 될 수 있는 banId가 모인 banList가 중복되면 안된다는 것입니다.

dfs를 인덱스 순으로 돌리기 때문에, banList에 push되는 userId는 '순서'가 유지될 것입니다.

이를 이용해서 banList의 사이즈가 ban 사이즈와 같아졌을 때 banList에 푸쉬된 스트링값들을 '따로 처리'해주면

쉽게 중복을 확인할 수 있습니다.

저는 '따로 처리'를 그냥 string 변수에 ' ' 간격으로 덧붙여서 문자열로 만든 후에

set을 이용해서 찾아낸 답이였는지 중복을 확인해주는 방법으로 문제를 해결하였습니다.

이는 현재 문제의 범위가 작아서 가능한 것이고

범위가 큰 문제에서는 스트링을 임의의 숫자같은 것으로 변경해주거나 등등의 방법으로 '따로 처리'를 할 수 있습니다.

 

#include <string>
#include <vector>
#include <iostream>
#include <set>
using namespace std;

vector<string> user;
vector<string> ban;
vector<string> banlist;
bool usingban[9];
int answer;
set<string> visit;

void dfs(int idx){
    if(banlist.size() == ban.size()){
        
        string visitid = "";
        for(auto i : banlist){
            visitid += i;
            visitid += ' ';
        }
        
        if(visit.find(visitid) == visit.end()){
            answer++;
            visit.insert(visitid);
        }
        
        return;
    }
    
    if(idx < user.size()){
        string user_id = user[idx];
        for(int i = 0; i<ban.size(); i++){
            if(usingban[i]) continue;
            string ban_id = ban[i];
            if(user_id.size() == ban_id.size()){
                bool checkban = true;
                for(int j = 0; j<ban_id.size(); j++){
                    if(ban_id[j] != '*' && (ban_id[j] != user_id[j])){
                        checkban = false;
                        break;
                    }
                }
                if(checkban){
                    usingban[i] = true;
                    banlist.push_back(user_id);
                    dfs(idx+1);
                    usingban[i] = false;
                    banlist.pop_back();
                }
            }
        }
        dfs(idx+1);
    }
}

int solution(vector<string> user_id, vector<string> banned_id) {
    
    user = user_id;
    ban = banned_id;
    
    dfs(0);
    
    return answer;
}