(c++) 프로그래머스 "불량사업자 (level-3)"

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

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

---

#include <string>
#include <vector>
#include <set>
#include <iostream>
#include <algorithm>

using namespace std;
set<string> s;
bool visited[8] = { false };
vector<string> user_id, banned_id;
bool check(string u_id, string cmp) {
	if (u_id.size() == cmp.size()) {
		for (int k = 0; k < cmp.size(); k++) {
			if (cmp[k] == '*') {
				continue;
			}
			else if (cmp[k] != u_id[k]) {
				return false;
			}
		}
		return true;
	}
	return false;
}

void dfs(int i, string str) {
	if (i == banned_id.size()) {
		sort(str.begin(), str.end());
		s.insert(str);
		return;
	}
	string b_id = banned_id[i];
	for (int k = 0; k < user_id.size(); k++) {
		if (check(user_id[k], b_id) && !visited[k]) {
			visited[k] = true;
			dfs(i + 1, str + to_string(k));
			visited[k] = false;
		}
	}
}

int solution(vector<string> u, vector<string> b) {
	user_id.assign(u.begin(), u.end());
	banned_id.assign(b.begin(), b.end());
	dfs(0, "");
	return s.size();
}

테스트 5에서 시간초과로 힘들었던 문제

처음에는 조합으로 풀었는데 sort 사용하니 금방 풀었다.