[DFS 순열/DFS 반복(조합, 순열)] 프로그래머스 불량 사용자 C++

 

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

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

1. DFS 순열

banned_id 배열 인덱스에 user_id 값((banned_id 배열 크기)개 선택)

set으로 조합 확인

#include <string>
#include <vector>
#include <set> // set 이용

using namespace std;

set<string> s; // 문자열 조합 저장
bool visited[8] = {false, }; // 문자열 사용 표시 저장

void dfs(int b, vector<string> user_id, vector<string> banned_id) {
    if (b == banned_id.size()) {
        string str = "";
        for (int i = 0; i < user_id.size(); i++) {
            if (visited[i])  str += i; // 문자열 조합
        }
        s.insert(str); // 문자열 조합 중복 제외 저장
    }

    for (int i = 0; i < user_id.size(); i++) {
        if (visited[i]) continue; // 이미 제재된 아이디 제외
        if (user_id[i].size() != banned_id[b].size()) continue; // 문자열의 길이가 다르면 해당 제재 아이디와 관계 없으므로 제외
        
        bool temp = true;
        for (int j = 0; j < user_id[i].size(); j++) {
            if ((user_id[i][j] == banned_id[b][j]) || (banned_id[b][j]=='*')) continue;
            else { // 한 문자라도 서로 다르거나 ‘*’가 아닐 때
                temp = false;
                break;
            }
        }

        if (temp == true) { // 제재 사용자에 포함되는 아이디
            visited[i] = true; // 문자열 사용 표시
            dfs(b + 1, user_id, banned_id);
            visited[i] = false; // 문자열 사용 표시 해제
        }
    }
}
int solution(vector<string> user_id, vector<string> banned_id) {
    int answer = 0;
    dfs(0, user_id, banned_id);
    answer = s.size(); // 문자열 조합의 개수
    
    return answer;
}

#include <string>
#include <vector>
#include <set> // set 이용

using namespace std;

set<string> dfs(int b, bool* visited, set<string> s, vector<string> user_id, vector<string> banned_id) {
    if (b == 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].size() != banned_id[b].size()) continue; // 문자열의 길이가 다르면 해당 제재 아이디와 관계 없으므로 제외
        
        bool temp = true;
        for (int j = 0; j < user_id[i].size(); j++) {
            if ((user_id[i][j] == banned_id[b][j]) || (banned_id[b][j]=='*')) continue;
            else { // 한 문자라도 서로 다르거나 ‘*’가 아닐 때
                temp = false;
                break;
            }
        }

        if (temp == true) { // 제재 사용자에 포함되는 아이디
            visited[i] = true; // 문자열 사용 표시
            s = dfs(b + 1, visited, s, user_id, banned_id);
            visited[i] = false; // 문자열 사용 표시 해제
        }
    }

    return s;
}

int solution(vector<string> user_id, vector<string> banned_id) {
    int answer = 0;
    int temp = 0;

    set<string> s; // 문자열 조합 저장
    bool visited[8] = {false, }; // 문자열 사용 표시 저장

    s = dfs(0, visited, s, user_id, banned_id);
    answer = s.size(); // 문자열 조합의 개수
    
    return answer;
}

 

2. DFS 반복(조합, 순열)

#include <string>
#include <vector>

using namespace std;

int answer;
int order[8]; // 사용자 아이디 조합 인덱스
bool existed; // 사용자 아이디 조합이 전부 제재 아이디와 일치하는지 여부
bool visited[8]; // 순열 방문 확인

void check(int depth, vector<string> user_id, vector<string> banned_id) {
    if (depth == banned_id.size()) {
        existed = true;
        answer++;
        return;
    }
   
    for (int i=0; i<banned_id.size(); i++) {
        if (existed) return;
        if (visited[i]) continue;
        if (user_id[order[depth]].size() != banned_id[i].size()) continue;
        bool temp = true;
        for (int j=0; j<banned_id[i].size(); j++) {
            if ((user_id[order[depth]][j] == banned_id[i][j]) || (banned_id[i][j]=='*')) continue;
            else {
                temp = false;
                break;
            }
        }
        if (temp) {
            visited[i] = true;
            check(depth + 1, user_id, banned_id);
            visited[i] = false;
        }
    }
}

void dfs(int b, int num, vector<string> user_id, vector<string> banned_id) {
    if (b == banned_id.size()) {
        existed = false;
        check(0, user_id, banned_id);
    }

    for (int i = num; i<user_id.size(); i++) {
        order[b] = i;
        dfs(b + 1, i + 1, user_id, banned_id);
    }
}
int solution(vector<string> user_id, vector<string> banned_id) {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    dfs(0, 0, user_id, banned_id);
    return answer;
}