[C++] 프로그래머스 2019 카카오 개발자 겨울 인턴십 - 불량 사용자

(1시간 반) DFS 쓰면 당연히 시간초과 날 줄 알았는데 통과. 경우의 수만 구하는 방법이 있을 줄 알았다..

같은 조합인지 확인할려고 정렬 후 하나의 string으로 묶어서 저장했는데 다른 사람 풀이를 보니까 user_id 배열의 크기가 8까지인걸 이용하면 훨씬 쉽게 풀 수 있는걸 알았다.

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

using namespace std;


vector<vector<string>> mapping;
set<string> answer;

void combineID(int idx, vector<string> combine) {
	if (idx == mapping.size()) {
		sort(combine.begin(), combine.end());
		string tmp = "";
		for (int i = 0; i < combine.size(); i++) {
			tmp += combine[i];
		}
		answer.insert(tmp);
		return;
	}

	for (int i = 0; i < mapping[idx].size(); i++) {
		bool check = true;
		for (int j = 0; j < combine.size(); j++) {
			if (mapping[idx][i] == combine[j]) {
				check = false;
				break;
			}
		}

		if (check) {
			combine.push_back(mapping[idx][i]);
			combineID(idx + 1, combine);
			combine.pop_back();
		}
	}
}

int solution(vector<string> user_id, vector<string> banned_id) {
	for (int i = 0; i < banned_id.size(); i++) {
		vector<string> tmp;
		for (int j = 0; j < user_id.size(); j++) {
			if (banned_id[i].size() != user_id[j].size()) continue;

			bool check = true;
			for (int k = 0; k < banned_id[i].size(); k++) {
				if (banned_id[i][k] != user_id[j][k]) {
					if (banned_id[i][k] != '*') {
						check = false;
						break;
					}
				}
			}

			if (check) {
				tmp.push_back(user_id[j]);
			}
		}
		mapping.push_back(tmp);
	}

	vector<string> combine;
	combineID(0, combine);

	return answer.size();
}