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

✔️ 문제

• 문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/64064
• 2019 카카오 개발자 겨울 인턴 코딩 테스트 기출문제

✔️ 풀이

• 불량 사용자 목록에 매핑 가능한 응모자 아이디 목록의 개수(경우의 수)를 구하는 문제다.
• 주어진 응모자 아이디 목록에서 불량 사용자 아이디 목록 개수 만큼 아이디를 추출한후 매핑이 가능한지 확인하면 된다.
• 응모자 아이디 목록에서 불량 사용자 아이디 목록 개수 만큼 뽑는 순열을 구현한다.
• 순열을 뽑을 때마다 주어진 불량 사용자 아이디 목록과 매핑 가능한지 확인한다.
• 매핑이 가능하면, 경우의 수(정답)를 증가 시킨다.
• 문제에서 제제 아이디 목록은 중복되면 안 된다고 했으므로(제제 아이디들이 나열된 순서와 관계없이), set을 통해 중복된 경우를 체크하고 경우의 수에서 제외한다.
• set을 통해 제제 아이디 목록 중복 체크를 할경우, 제제 아이디 목록을 정렬 하고 set에 넣어줘야한다.(그래야 순서 상관없이 목록 중복을 체크할 수 있다.)

👨🏻‍💻 소스 코드

#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
#include <set>
using namespace std;

int answer;
bool check[10];
vector<string> g_user_id;
vector<string> g_banned_id;
vector<string> candi;
set<vector<string>> s;

void permutation() {
	if (candi.size()==g_banned_id.size()) {
		vector<string> sortedCandi = candi;
		sort(sortedCandi.begin(), sortedCandi.end());

		if (s.count(sortedCandi)) return;

		for (int i = 0; i < g_banned_id.size(); i++) {
			if (candi[i].size() != g_banned_id[i].size()) return;
			for (int j = 0; j < candi[i].size(); j++) {
				if (g_banned_id[i][j] == '*') continue;
				if (candi[i][j] != g_banned_id[i][j]) return;
			}
		}

		s.insert(sortedCandi);
		answer++;
		return;
	}

	for (int i = 0; i < g_user_id.size(); i++) {
		if (!check[i]) {
			check[i] = true;
			candi.push_back(g_user_id[i]);
			permutation();
			candi.pop_back();
			check[i] = false;
		}
	}
}

int solution(vector<string> user_id, vector<string> banned_id) {
	g_user_id = user_id;
	g_banned_id = banned_id;
	permutation();
	return answer;
}

✔️ 문제 회고

• 가능한 경우의 수를 찾는 문제다.
• 순열을 활용해서 풀 수 있다.