[프로그래머스, C++] 불량 사용자

문제 링크

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

 

 

 

풀이

재귀 DFS로 풀었다.

 

// check_equal 함수

불량 사용자인지 판별하는 함수다.

'*'에 대한 처리를 한다.

 

// solution 함수

banned_id가 각각 어떤 것에 해당되는지 미리 "vv" vector 컨테이너에 담는다.

"vv" 컨테이너는 user_id의 인덱스로 담는다.(중복 검사하는데 string보다 정수 하나 비교하는게 더 간편하기 때문에)

그리고 DFS 진행한다.

 

// dfs 함수

중복을 제거하기 위해 <set>을 사용하였고 재귀를 돌면서 중복에 대해서는 dfs 함수를 재호출하지 않도록 했다.

하지만, 불량사용자 목록 전체를 보았을 때는 중복에 대한 처리가 안된다.

예를 들어, {1, 0, 2, 3}과 {0, 1, 2, 3}은 중복된 것이라고 봐야하기 때문에 string을 이용하여 중복을 처리한다.

참고로, set이 input이 될 때마다 알아서 정렬이 되기 때문에 string에 대해서 sort 해줄 필요는 없었다.

 

 

 

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

using namespace std;

// user_id 배열은 1 이상 8 이하
// 서로 중복 X, 각 원소들 길이 1 이상 8 이하
// banned_id 배열은 1 이상 user_id보다 적다.
// '*' 하나 이상 포함
// 모든 아이디는 알파벳 소문자와 숫자로만 이루어짐

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

int dfs(vector<string>& list, vector<vector<int>> vv, set<int> visit, int index){
    if(index == vv.size()){
        string s = "";
        for(auto e: visit) s += '0' + e;
        
        // 전체 중복 검사
        for(int i=0; i<list.size(); i++){
            if(list[i]==s) return 0;        // 중복이면 갯수 추가 X
        }
        list.push_back(s);      // 중복 아닌거 push
        return 1;     // 중복 아니면 갯수 추가
    }

    int count = 0;
    for(int i=0; i<vv[index].size(); i++){
        if(visit.find(vv[index][i]) == visit.end()){
            visit.insert(vv[index][i]);
            count+=dfs(list, vv, visit, index+1);         // 중복이 아닌 것만
            visit.erase(vv[index][i]);
        }
    }
    return count;
}

int solution(vector<string> user_id, vector<string> banned_id) {
    int answer = 0;
    const int uSize = user_id.size();
    const int bSize = banned_id.size();
    vector<vector<int>> vv(bSize);
    
    // 각 banned_id마다 같은 값들 정리
    for(int i=0; i<bSize; i++){
        for(int j=0; j<uSize; j++){
            if(check_equal(banned_id[i], user_id[j])){
                vv[i].push_back(j);         // 인덱스를 저장
            }
        }
    }
    
    // DFS
    set<int> s;     // 원소 1개의 중복 검사
    vector<string> list;        // 전체 중복 검사
    answer = dfs(list, vv, s, 0);         // index: 0부터 시작
    
    return answer;          // 제재 아이디 목록 경우의 수 가짓수
}