프로그래머스 : 불량 사용자

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

프로그래머스

 

처음에는 경우의 수 문제처럼 접근했다. (그냥 수학계산으로만 해결하려고함)

각 banned_id마다 가능한 user_id 경우의수를 찾고, 다 곱해줬는데.... 해결이 안됐다!

 

두번째 테스트 케이스 같은 경우를 생각해보면, 

내가 처음 생각한 방법대로면 *rodo 2개, *rodo 2개, ****** 2개 해서 총 8개라는 결과가 나온다

하지만...

실제로는 이런 경우의 수만 가능하게 된다!ㅎㅎ..

 

그래서 그냥 완전탐색 DFS로 해결했다..ㅎㅎ..

 

평범하게 제제 아이디 리스트를 dfs로 만들고,

중복이 있으면 넣지않고 중복이 없으면 추가해주는 방법으로 구현했다.

마지막에 모든 제제아이디 리스트의 리스트의 길이를 반환해주면 된다.

 

확인할 때 sort를 해주는 이유는... sort가 없을 때 확인하려면 for가 한번 더 필요할것같았기 때문이다! ㅎ..

 

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

using namespace std;
vector<string> banned_list;
vector<vector<string>> result;


bool is_banned(string id, string ban){
    if(id.size() != ban.size()){
        return false;
    }
    for(int i = 0; i<id.size(); i++){
        if(id[i] == ban[i] || ban[i] == '*'){
            continue;
        }
        return false;
    }
    return true;
}

bool is_in(vector<string> list){
    for(int i = 0; i<result.size(); i++){
        bool isok = false;
        for(int j = 0; j<result[i].size(); j++){
            if(result[i][j].compare(list[j]) != 0){
                isok = true;
                break;
            }
        }
        if(!isok){
            return false;
        }
    }
    return true;
}

void printvec(vector<string> vec){
    for(int i = 0; i<vec.size(); i++){
        cout << vec[i] << " ";
    }
    cout << endl;
}

void dfs(int index, vector<string> user_id, vector<string> ban){
    if(index == (int)banned_list.size()){
        sort(ban.begin(), ban.end());
        if(is_in(ban)){
            
            result.push_back(ban);
        }
        
        return;
    }
    for(int i = 0; i<user_id.size(); i++){
        if(is_banned(user_id[i], banned_list[index])){
            vector<string> next_ids = user_id;
            vector<string> next_ban = ban;
            next_ban.push_back(user_id[i]);
            next_ids.erase(next_ids.begin() + i, next_ids.begin() + i+1);
            dfs(index+1, next_ids, next_ban);
        }
    }
}

int solution(vector<string> user_id, vector<string> banned_id) {
    
    banned_list = banned_id;
    
    dfs(0, user_id, {});
    
    return (int)result.size();
}