[프로그래머스 2019 카카오 개발자 겨울 인턴십] 불량 사용자 (DFS, 조합) [C++]

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

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

 

불량 사용자로 판단되는 아이디의 경우를 찾는 문제이다.

1. *로 일부분 마스킹된 banned_id와 user_id가 일치하는지 확인해야 한다.

 - 이건 문자열 하나씩 보면서 일치하는지, 불일치하는지 확인하면 된다. *인 경우는 패스, 길이도 봐야 한다.

2. 찾은 user_id로 중복을 제외하고 경우의 수를 찾아야 한다.

 - 나는 처음에 각 banned_id에 해당하는 user_id를 찾았어서, 조합으로 풀었는데 중복을 제거하고 예외를 처리하는데 코드가 길어졌다.

 - DFS를 사용하면 좀 더 편리하게 찾을 수 있다.

---

1. 조합 이용

 - 각 banned_id에 일치하는 user_id를 2차원 벡터에 각각 저장해주었다.

banned_id 1 = a b c

banned_id 2 = b c

banned_id 3 = a c d 이런 식으로 벡터에 넣어주었다.

그다음 조합을 돌면서 경우를 찾았다. 이렇게 만들어 낼 경우 뽑은 id는 또 뽑는 경우는 제외가 되지만 a b c 나 b a c와 같은 경우가 등장한다.

이 경우 역시 없애줘야 해서 정렬을 해준 후에 문자열에 저장해주고, set을 통해서 중복을 체크해주었다.

풀고 나서 보니 많이 비효율적인 방법 같다.

#include <string>
#include <vector>
#include <iostream>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>

using namespace std;

vector<vector<string>> banList;
unordered_set<string> answerList;
unordered_map<string, bool> check;

void backTracking(int next, int depth, int limit, vector<string>& list){
    if(depth == limit){
        vector<string> sortingList = list;
        sort(sortingList.begin(), sortingList.end());
        string temp = "";
        for(auto k : sortingList)
            temp += k;
        answerList.insert(temp);
        return;
    }

    for(int i = next ; i < banList.size() ; i++){
        for(int j = 0 ; j < banList[i].size() ; j++){
            string target = banList[i][j];
            if(check.find(target) == check.end()){ // 못찾음
                check[target] = true;
                list.push_back(target);
                backTracking(i+1, depth+1, limit, list);
                list.pop_back();
                check.erase(target);
            }
        }
    }
}

int solution(vector<string> user_id, vector<string> banned_id) {
    int answer = 0;
    for(auto ban : banned_id){
        vector<string> tempBan;
        for(auto user : user_id){
            int flag = true;
            if(ban.size() != user.size())
                continue;
            for(int i = 0 ; i < ban.size() ; i++){
                if(ban[i] == '*')
                    continue;
                if(ban[i] != user[i]){
                    flag = false;
                    break;
                }
            }
            if(flag){
                tempBan.push_back(user);
            }
        }
        if(tempBan.size())
            banList.push_back(tempBan);
    } // 여기까지 각 banned_id에 해당하는 user_id를 벡터에 저장해주었다.
    vector<string> v;
    backTracking(0, 0, banList.size(), v);

    return answerList.size();
}

 

2. DFS 

- 다른 분의 풀이를 보고 다시 풀어본 방법이다.

나는 미리 banned_id에 해당하는 user_id를 각각 만들어주고 그걸 조합을 돌면서 최종 목록을 만들어냈다.

이 방법은 미리 만들어내지 않고 DFS를 돌면서 그때 판단해서 나아가는 방법이다.

또한 문자열을 사용한 use배열을 이용했는데, 이 배열을 이용해서 i는 0부터 돌면서 이용한 id를 붙여주면 자연스럽게

a b c나 b a c와 같은 케이스는 나오지 않는다. 무조건 앞에서부터 붙이니 둘 다 a b c가 될 것이다.

depth는 banned_id 목록으로 고정되어 있고, 해당 목록에 user_id를 붙이면서 깊이 탐색을 진행한다.

#include <string>
#include <vector>
#include <unordered_set>
#include <iostream>

using namespace std;

bool use[10];
unordered_set<string> check;

bool searchBan(string & a, string & b){
    if(a.size() != b.size())
        return false;
    for(int i = 0 ; i < a.size() ; i++){
        if(a[i] != b[i] && a[i] != '*')
            return false;
    }
    return true;
} // 문자열이 일치하는지?

void DFS(int now, vector<string> & user_id, vector<string> & banned_id){
    if(now == banned_id.size()){ // 도착하면 사용한 id를 붙여서 중복 검사까지 진행한다
        string temp = "";
        for(int i = 0 ; i < user_id.size() ; i++){
            if(use[i])
                temp += user_id[i];
        }
        
        if(check.find(temp) == check.end()){
            //cout<<temp<<"\n";
            check.insert(temp);
        }
        return;
    }
    
    // id는 처음부터 계속 돌리고, banned_id를 기준으로 dfs를 진행한다.
    for(int i = 0 ; i < user_id.size() ; i++){
        if(searchBan(banned_id[now], user_id[i]) && !use[i]){
            use[i]= true;
            DFS(now+1, user_id, banned_id);
            use[i] = false;
        }
    }
}

int solution(vector<string> user_id, vector<string> banned_id) {
    int answer = 0;
    
    DFS(0, user_id, banned_id);
    
    
    return check.size();
}