[프로그래머스] 불량 사용자 [C++][lv.3] 2019 카카오 개발자 겨울 인턴

 

 

#문제 해결 방법

 

우선, 이름의 배열 크기가 8이기 때문에 

각자 이름끼리 맞는지 확인까지 해도

완전탐색으로 풀 수 있다는 걸 쉽게 알 수 있다.

 

때문에 설계를 하자면

1. 이름끼리 비교하는 함수를 만든다

2. 이걸 전체 순회하는 dfs 함수를 만든다

 

라는 설계가 가능하다 

 

우선 이름이 맞는지 확인하는 함수는 

 

bool nameCmp(string user, string banned){
    
    if(user.length() != banned.length()){
        return false;
    }else{
        for(int i=0; i<user.length(); ++i){
            if(banned[i] != '*' && user[i] != banned[i]){
                return false;
            }
        }
    }
    
    return true;
}

 

로 쉽게 만들 수가 있다.

길이가 다르거나

*이 아닌다 문자가 다른경우에 false 를 리턴한다

 

 

이제 dfs 함수를 만들어야 되는데 이부분이 조금 고민이 된다

 

여기서 탐색 포커싱을

banned_id에 맞춰야 된다

 

각 banned_id에 매칭되는 id를 찾았다면 다음 banned id 로 넘어가면 된다

 

 

그리고 여기서 까다로운 부분이 하나 더 있는데.

 

각각의 정답으로 고른 정답에서 

중복되는 답이 있을 수 있기 때문이다.

 

같은 아이디가 순서만 다른 정답이 있을 수 있다.

 

이 부분은 set을 사용해서 해결할 수 있는데

 

다른 분들 같은경우에는 set에서 find 해서 없는경우에만 insert 하도록 하는 경우가 일반적인 것 같다.

 

나는 set<set<string>> result  // 이중 셋을 사용해서 중복을 제거했다.

이중 셋을 사용하면 중복을 편하게 제거할수 있으니 유용한 팁이라고 할 수 있다.

 

 

#전체 코드

 

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

using namespace std;

//dfs 로 모든 조합을 살펴보고
//이름을 비교하는 함수도 만들어야함


bool nameCmp(string user, string banned){
    
    if(user.length() != banned.length()){
        return false;
    }else{
        for(int i=0; i<user.length(); ++i){
            if(banned[i] != '*' && user[i] != banned[i]){
                return false;
            }
        }
    }
    
    return true;
}

void dfs(vector<string>& user_id, vector<string>& banned_id, vector<bool>& visited, set<set<string>>& result, set<string>& currentSet, int index) {
    if (index == banned_id.size()) {
        result.insert(currentSet);
        return;
    }
    for (int i = 0; i < user_id.size(); ++i) {
        if (!visited[i] && nameCmp(user_id[i], banned_id[index])) {
            visited[i] = true;
            currentSet.insert(user_id[i]);
            dfs(user_id, banned_id, visited, result, currentSet, index + 1);
            currentSet.erase(user_id[i]);
            visited[i] = false;
        }
    }
}


int solution(vector<string> user_id, vector<string> banned_id) {
    
    set<set<string>> result;
    set<string> currentSet;
    vector<bool> visited(user_id.size(), false);
    
     dfs(user_id, banned_id, visited, result, currentSet, 0);

    return result.size();
}