[기출 상] 프로그래머스 불량 사용자

[문제]

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

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

[풀이]

먼저 dfs를 이용하여 풀 수 있다. 

이미 방문했거나 길이가 다른 경우를 패스하고, user_id[i]의 문자를 하나씩 비교해줘 user_id와 banned_id가 *부분을 제외하고 전부 일치하면 visited[]배열에 true를 저장, 방문 표시를 해준다. 이후 비교해야 할 banned_id index인 bsize를 하나 증가시켜 dfs를 호출한다. 만약 bsize가 banned_id의 size와 일치하면 제재 아이디가 될 수 있는 조합이 나온 것이므로 set에 저장해준다. 중복된 제재 아이디 조합을 제거하기 위하여 set을 이용하고, 최종 답은 제재 아이디의 조합의 개수인 set의 사이즈가 된다.

 

[코드]

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

using namespace std;

set<string> dfs(int bsize, bool* visited, set<string> s, vector<string> user_id, vector<string> banned_id){
    if(bsize==banned_id.size()){
        string str = "";
        for(int i=0; i<user_id.size(); i++){
            if(visited[i]) 
                str += i; //제재 아이디 인덱스를 오름차순으로 저장
        }
        s.insert(str); // 조합. 중복 제거.
        return s;
    }
    for(int i=0; i<user_id.size(); i++){
        if(visited[i])
            continue;
        if(user_id[i].length() != banned_id[bsize].length())
            continue;
        bool check = true;
        for(int j=0; j<user_id[i].size(); j++){ //모든 user_id[i]의 문자를 비교
            if(user_id[i][j] == banned_id[bsize][j] || banned_id[bsize][j]=='*')
                check = true;
            else {
                check = false;
                break;
            }
        }
        if(check){
            visited[i] = true;
            s = dfs(bsize+1, visited, s, user_id, banned_id);
            visited[i] = false; //방문 해제
        }

    }
    
    return s;
    
}

int solution(vector<string> user_id, vector<string> banned_id) {
    //dfs.
    int answer = 0;
    set<string> s;
    bool visited[8] = {false, }; //방문 안함.

    s = dfs(0, visited, s, user_id, banned_id);
    answer = s.size();
    return answer;
}