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

분류 

dfs, 구현

요구사항

불량 사용자 중 제제 아이디에 해당하는 쌍이 몇개 인지 구하기

풀이

나의 풀이는

1. 불량 사용자를 조합으로 n개 뽑는다

2. 제제 아이디를 permutation하여서 뽑은 n개랑 제제 아이디가 해당하는지 확인한다.

 

 

1. 불량 사용자 중에서 제제 아이디의 크기만큼 n개를 고른다

2. 제제 아이디 permutation하여서 순열구한다

3. 고른 불량 사용자가 순열에 해당하는지 확인하여 준다

 

#include <string>
#include <vector>
#include <iostream>
#include <string.h>
#include <math.h>
#include <algorithm>
using namespace std;
vector<int> v;
int visit[10];
int Wvisit[10];
int play[10];
int ans = 0;
int Svisit[10];
vector<int> v1;
vector<int> sv[8 * 7 * 6 * 5 * 4 * 3 * 2];
int num1 = 0;
vector<string> a;
vector<string> b;

bool check(string a, string b) {
	int i = 0;
	int j = 0;
	int asize = a.size();
	int bsize = b.size();
	int Size = max(asize, bsize);
	if (asize != bsize) return false;
	for (int i = 0; i < Size; i++) {
		if (a[i] != b[i]) {
			if (b[i] == '*') continue;
			return false;
		}
	}
	return true;

}
void secondper(int cnt, vector<string> banned_id) {
	if (cnt == banned_id.size()) {
		for (int i = 0; i < banned_id.size(); i++) {
			sv[num1].push_back(v1[i]);
		}
		num1++;
		return;
	}
	for (int i = 0; i < banned_id.size(); i++) {
		if (Svisit[i] == 0) {
			Svisit[i] = 1;
			v1.push_back(i);
			secondper(cnt + 1, banned_id);
			v1.pop_back();
			Svisit[i] = 0;
		}
	}
}
void per(int cnt, int num, int psize, int wsize, vector<string> user_id, vector<string> banned_id) {

	if (cnt == banned_id.size()) {
		int count = 0;
		cout << num1 << endl;
		for (int i = 0; i <= num1 - 1; i++) {
			int flag = 0;
			for (int j = 0; j < wsize; j++) {
				if (check(user_id[v[j]], banned_id[sv[i][j]])) {
					continue;
				}
				else {
					flag = 1;
					break;
				}
			}
			if (flag == 0)
			{
				ans++;
				break;
			}
		}
		return;
	}
	for (int i = num; i < psize; i++) {
		if (visit[i] == 0) {
			visit[i] = 1;
			v.push_back(i);
			per(cnt + 1, i + 1, psize, wsize, user_id, banned_id);
			v.pop_back();
			visit[i] = 0;
		}
	}
}
int solution(vector<string> user_id, vector<string> banned_id) {
	int answer = 0;
	secondper(0, banned_id);
	per(0, 0, user_id.size(), banned_id.size(), user_id, banned_id);
	answer = ans;
	return answer;
}