문제 출처

1. 문제설명

  • 아이디(id) 리스트, 제재 아이디(ban) 리스트가 주어진다.
  • ban에 매핑되는 id를 제외시키려고 할 때의 경우의 수를 구하는 문제


2. 입/출력

  • 입력
    • 이벤트 응모자 아이디 목록이 담긴 배열 user_id
    • 불량 사용자 아이디 목록이 담긴 배열 banned_id
  • 출력
    • 당첨에서 제외되어야 할 제재 아이디 목록은 몇가지 경우의 수가 가능한 지 return


3. 문제 분류

  • Simulation, DFS


4. 알고리즘 설계

  • N이 최대 8이므로, 3중 반복문으로 매칭되는 문자열 탐색
    • id를 하나씩 꺼내 모든 ban과 비교한다.
    • flag 변수를 사용하여, 하나라도 일치하지 않으면 저장 대상이 아니다.
    • ‘*‘은 조커같은 개념으로, 어떤 글자가 매칭되도 상관없다.
  • ban은 중복 가능하다.
    • 즉 1번째 ban과 2번째 ban은 서로 다른 조합이다.
    • 일치한다면 전부 저장해야 한다.
  • dfs를 수행하면서 조합을 만든다.
    • 방문 배열을 통해 사용 여부 체크
      • vis1은 id를 사용했는지, vis2는 ban을 사용했는지
    • 다음 dfs를 수행한다.
      • 개수를 1 증가시키고, idx를 전달해서 중복을 피한다.
      • 현재 문자열에 id의 인덱스 번호를 concat하게 된다.
        • 즉 (id1, id2, id3) 이라면 “123”이 된다.
        • N이 최대 8이기 때문에 2자리 숫자가 없어 가능한 로직이다.
    • 조합의 구성의 수가 ban의 최대 개수가 된다면 종료 조건이다.
      • 여기까지 진행되었을 때, id의 조합이 같을 수가 있다.
        • 궁금하다면, 예제 2번을 시뮬레이션 해보자
      • unordered_map을 통해 중복이 있다면 정답값 + 1을 하지 않는다.


5. 전체 코드

#include <bits/stdc++.h>
using namespace std;

vector<pair<int, int>> v;
unordered_map<string, int> MAP;
int SZ, ans;
bool vis1[8], vis2[8];

void dfs(int cnt, int s, string tmp) {
	if (cnt == SZ) {
		if (MAP[tmp] == 0) {
			ans++;
			MAP[tmp]++;
		}

		return;
	}

	for (int i = s; i < v.size(); i++) {
		auto cur = v[i];

		if (vis1[cur.first] || vis2[cur.second]) continue;

		vis1[cur.first] = true;
		vis2[cur.second] = true;
		dfs(cnt + 1, i + 1, tmp + to_string(cur.first));
		vis1[cur.first] = false;
		vis2[cur.second] = false;
	}
}

int solution(vector<string> user_id, vector<string> banned_id) {
	int answer = 0;
	SZ = banned_id.size();

	for (int u = 0; u < user_id.size(); u++) {
		for (int b = 0; b < banned_id.size(); b++) {
			string user = user_id[u];
			string ban = banned_id[b];

			if (user.size() != ban.size()) continue;

			bool flag = false;
			int i = 0, j = 0;
			while (i == j && i < user.size()) {
				if (user[i] == ban[j] || ban[i] == '*') {
					flag = true;
					i++, j++;
				}
				else {
					flag = false;
					break;
				}
			}

			if (flag)
				v.push_back({ u, b });
		}
	}

	dfs(0, 0, "");
	return ans;
}