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

프로그래머스 불량 사용자 문제 풀이입니다.

Problem:

불량 사용자

이 문제는 모든 경우의수를 다 따져야 하는 전형적인 DFS문제이다.

우선 내가 가장 먼저 한 작업은 응모자 아이디와 매칭될 수 있는 불량사용자 아이디를 추출해내는 것이였다. 따라서 dfs를 들어가기 전에 우선 매칭되는 아이디 리스트를 먼저 구한 뒤 dfs로 들어갔다.

이후에 일반적으로 dfs를 돌렸더니 중복값들이 계속해서 카운트되는 문제가 발생하였다.

그래서 나는 set을 활용하여 중복을 제거해주었다.

소스는 다음과 같다.

Source Code(C++) :

#include <string>
#include <vector>
#include <set>
using namespace std;

vector<string> possible_list[100], temp;
set<set<string>> result;
bool visit[10] = {false,};
int answer = 0;

int banned_size;


void dfs(int cnt,vector<string>& user_id) {
	if (cnt == banned_size) {
		set<string> tmp;
		for (string t : temp) {
			tmp.insert(t);
		}
		if (result.count(tmp) == 0) {
			answer++;
			result.insert(tmp);
		}
	}

	for (int i = 0; i < possible_list[cnt].size(); i++) {
		for (int j = 0; j < user_id.size(); j++) {
			if (!visit[j] && possible_list[cnt][i] == user_id[j]) {
				visit[j] = true;
				temp.push_back(user_id[j]);
				dfs(cnt + 1, user_id);
				temp.pop_back();
				visit[j] = false;
			}
		}
	}
}

int solution(vector<string> user_id, vector<string> banned_id) {
	
	int idx = 0;
	banned_size = banned_id.size();
	for (string banned : banned_id) {
		for (string user : user_id) {
			bool chk = true;
			if (banned.length() != user.length())continue;
			for (int i = 0; i < user.length(); i++) {
				if (user[i] != banned[i] && banned[i] != '*') {
					chk = false;
					break;
				}
			}
			if (chk)
				possible_list[idx].push_back(user);
		}
		idx++;
	}

	dfs(0, user_id);


	return answer;
}

소스코드

이 외에도 제가 푼 문제들 소스코드는 다음 링크에 있습니다!!! 알고리즘 문제풀이