[Programmers] 불량 사용자

문제 링크입니다: https://programmers.co.kr/learn/courses/30/lessons/64064

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

 

알고리즘은 아래와 같습니다.

1. 불량 사용자 아이디에 해당하는 유저 아이디의 인덱스들을 벡터 배열 v에 넣어줍니다.

2. func 재귀 함수를 통해 나올 수 있는 유저 아이디의 인덱스 조합들을 정렬한 상태로 set에 넣어줍니다.

3. 2번에서 구한 set의 크기를 반환해주면 끝

 

	#include <string>
	#include <vector>
	#include <set>
	#include <iostream>
	#include <algorithm>
	using namespace std;
	const int MAX = 8;
	int N;
	set<string> result;
	vector<int> v[MAX];
	bool isIdentical(string userId, string bannedId)
	{
	if (userId.length() != bannedId.length())
	{
	return false;
	}
	for (int i = 0; i < userId.length(); i++)
	{
	if (bannedId[i] != '*' && userId[i] != bannedId[i])
	{
	return false;
	}
	}
	return true;
	}
	void func(int idx, string s, set<int> visited)
	{
	if (idx == N)
	{
	sort(s.begin(), s.end());
	result.insert(s);
	return;
	}
	for (int nameIdx : v[idx])
	{
	if (visited.find(nameIdx) == visited.end())
	{
	char c = nameIdx + '0';
	visited.insert(nameIdx);
	func(idx + 1, s + c, visited);
	visited.erase(nameIdx);
	}
	}
	}
	int solution(vector<string> user_id, vector<string> banned_id) {
	N = banned_id.size();
	for (int i = 0; i < banned_id.size(); i++)
	{
	for (int j = 0; j < user_id.size(); j++)
	{
	if (isIdentical(user_id[j], banned_id[i]))
	{
	v[i].push_back(j);
	}
	}
	}
	set<int> visited;
	func(0, "", visited);
	return result.size();
	}

view raw .cpp hosted with ❤ by GitHub

 

개발환경: Programmers IDE

 

지적, 조언, 질문 환영합니다! 질문 남겨주세요~