[2019 카카오 개발자 겨울 인턴십] 불량 사용자(C++)

불량 사용자

 

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

문제 설명

 

 - 이벤트 개발 담당자 "무지"는 불량 사용자 목록을 만들어 이벤트 담당자인 "프로도"에게 전달하려 한다.

 

 - 불량 사용자는 개인 정보 보호를 위하여 아이디의 일부 문자를 '*' 문자로 가려 전달했다.

   '*' 문자는 아이디당 최소 하나 이상을 사용하였다.

 

 - "무지"와 프로토"는 불량 사용자 목록에 매핑된 응모자 아이디를 제재 아이디 라고 부르기로 하였다.

 

 - 전체 아이디 목록과 불량 사용자 아이디 목록을 이용하여 제재 아이디가 될 수 있는 경우의 수를 구하여라.

 

---

입력 값

 

 - 전체 아이디 목록은 user_id 배열로 주어진다. ( 1<= user_id.size() <= 8)

 

 - user_id의 각 원소는 1이상 8이하의 문자열이다.

   (아이디는 중복되지 않고, 알파벳 소문자와 숫자로만 구성되어 있다.)

 

 - 불량 사용자 목록은 banned_id 배열로 주어진다. ( 1 <= banned_id.size() <= user_id.size() )

 

 - banned_id의 각 원소는 1이상 8이하의 문자열이다.

   (아이디는 '*' 문자를 하나 이상 포함하고 있고, 숫자, 문자, '*'로만 이루어져 있다.)

 

 - 불량 사용자 아이디 하나는 응모자 아이디 중 하나에 해당하고, 같은 응모자 아이디가 중복하여

   제재 아이디 목록에 들어가지 않는다.

 

 - 제재 아이디 목록들 중 나열된 순서와 상관없이 아이디 목록이 동일하다면 같은 것으로 처리한다.

 

---

 

예제

---

 

 

문제 분석

 

 - 각 불량 사용자 아이디에 맞는 유저 아이디 목록을 구한다.

 

 - 해당 목록은 DFS를 이용하여 구한다. ( 배열의 크기가 8이하이기 때문에 DFS를 이용해도 모두 구할 수 있다.)

 

 - 불량 사용자에 맞는 유저 아이디 목록을 바탕으로 겹치지 않는 모든 조합을 구하고, 그 조합의 개수를 반환한다.

 

 - 겹치지 않는 조합을 구하기 위하여 비트 마스크와 셋을 이용한다.

 

 

---

 

 

소스 코드

 

#include <bits/stdc++.h>

using namespace std;

set<int> s;

// search_id => 불량 사용자에 맞는 사용자 아이디 목록
// selectedIDNum => 기존 조합의 개수
// addNumber => 조합을 이루기 위해 선택된 값
// resultNumber => 조합된 값.
void dfs(vector<vector<int>> &search_id, int numberSize, int addNumber, int resultNumber)
{
	// 기존의 조합안에 새로 추가 될 값이 존재하는지 확인
	// &연산을 이용하여 last의 인덱스가 기존의 조합(resultNumber)에 
	// 존재하는지 확인,
	// 존재한다 => 중복 값이 있다.
	// 존재하지 않는다 => 중복 값이 없다.
	if (resultNumber & (1 << addNumber))
		return;

	// 기존 조합에 새로운 값 추가
	resultNumber |= (1 << addNumber);

	// 조합의 길이가 제재 아이디 목록 개수와 같은지 확인
	if (numberSize == search_id.size())
	{
		// 같다면, set에 추가.
		// set은 중복을 허용하지 않는다.
		s.insert(resultNumber);

		return;
	}

	for (int i = 0; i < search_id[numberSize].size(); i++)
	{
		dfs(search_id, numberSize + 1, search_id[numberSize][i], resultNumber);
	}

	return;
}

// 제재 아이디 찾기
void findstr(vector<string> user_id, string banned_id, vector<int> &v)
{
	bool isSame = false;
	for (int i = 0; i < user_id.size(); i++)
	{
		string uid = user_id[i];
		isSame = true;
		if (uid.size() != banned_id.size())
			continue;

		for (int j = 0; j < uid.size(); j++)
		{
			if (banned_id[j] == '*')
				continue;
			if (uid[j] != banned_id[j])
			{
				isSame = false;
				break;
			}
		}

		// 제재 아이디 찾기 성공.
		if (isSame)
			v.push_back(i);
	}
}



int solution(vector<string> user_id, vector<string> banned_id) {

	vector<vector<int>> search_id;
	for (int i = 0; i < banned_id.size(); i++)
	{
		vector<int> v;
		findstr(user_id, banned_id[i], v);
		search_id.push_back(v);
	}
	

	for (int i = 0; i < search_id[0].size(); i++)
	{

		dfs(search_id, 1, search_id[0][i],0);
	}


	return s.size();
}