프로그래머스 Level 3 불량사용자

불량사용자 (프로그래머스 Level 3)

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

처음에는 ‘수학’과 관련된 문제라 생각하여
‘조합’ 쪽의 문제로 접근하였으나
‘불량 사용자’ 배열의 각 요소는
‘응모자 아이디’ 쪽의 배열 요소를 ‘중복’하여 선택할 수 없기에

DFS와 백트래킹을 사용하여 풀게 되었다

구현 사항은 크게 2가지 였다

1. user 쪽 아이디가 ban 아이디에 해당하는지
   (isBannedId)
   
2. dfs를 이용하여 ‘ban’ 과 ‘user’ 측을 ‘선택’하였는지 체크
   해당 부분을 체크하기 위하여 2개의 visit 배열과
   set을 사용하여 해당 ‘조합’을 기록하였고
   이후 set의 크기를 답으로 return하도록 하였다
   

문제와는 상관없지만
문제를 풀 때, 가능하다면 ‘시간’에 좀 더 유의하며 문제를 풀어야겠다고
점점 더 생각이 든다

Code

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

using namespace std;

bool isBannedId(const string& user, const string& ban)
{
	const int uSize = user.size();
	const int bSize = ban.size();
	if (uSize != bSize)
		return false;

	for (int i = 0; i < uSize; i++)
	{
		if (ban[i] == '*')
			continue;

		if (user[i] != ban[i])
		{
			return false;
		}
	}

	return true;
}

void dfs(const vector<string>& user_id, const vector<string>& banned_id, vector<bool>& visited_ban, vector<bool>& visited_user, int count, set<vector<int>>& answer, int bIndex)
{
	const int bSize = banned_id.size();
	const int uSize = user_id.size();

	if (count == bSize)
	{
		vector<int> temp;
		for (int i = 0; i < uSize; i++)
		{
			if (visited_user[i])
				temp.push_back(i);
		}

		answer.insert(temp);
		return;
	}

	for (int i = bIndex; i < bSize; i++)
	{
		if (visited_ban[i] == true)
			continue;

		visited_ban[i] = true;

		for (int j = 0; j < uSize; j++)
		{
			if (visited_user[j] == true)
				continue;

			if (isBannedId(user_id[j], banned_id[i]) == true)
			{
				visited_user[j] = true;
				dfs(user_id, banned_id, visited_ban, visited_user, count + 1, answer, bIndex + 1);
				visited_user[j] = false;
			}
		}

		visited_ban[i] = false;
	}

}

int solution(vector<string> user_id, vector<string> banned_id) {
	vector<bool> visited_ban(banned_id.size(), false);
	vector<bool> visited_user(user_id.size(), false);
	set<vector<int>> s;

	dfs(user_id, banned_id, visited_ban, visited_user, 0, s, 0);

	return s.size();
}