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

문제

입출력 예시

풀이방법

1) 마스킹된 제재사용자 아이디로 가능한 유저 아이디를 체크한다.

2) 체크한 아이디들의 경우의 수를 따져준다. 

  2)-1 각각의 유저 아이디는 순서가 바뀐것은 하나로 취급한다.

3) 각 유저아이디의 조합의 경우를 count 해준다.

 

1) 이중포문으로 가능한 경우의 유저 아이디의 index를 추출하여 벡터에 담는다.

2) 체크한 아이디의 경우의 수를 따져주기 위해서 set 자료 구조를 이용 하였다. 

ex) 0123 = 0132가 같은 경우의 수 이기 때문이다. 단 set에 넣을 때는 0123과 0132일 떄 visit배열에 체크를 하였고 0부터 차례 대로 visit여부에 따라서 string으로 형변환하여 0132는 0123꼴로 나타내줬다 그래야만 set에 들어갈때 중복제거가 가능하기 때문이다.

3) 상기 set에 조합을 넣은 이유는 결론적으로 set에 들어간 크기가 전체 조합의 경우의 수와 같다는 것을 의미하기 때문

 

난이도

★★★☆☆

dfs를 구현하고 set에 어떻게 넣을지 고민을 좀 오래했음.. visit배열을 순서대로 추출하여 적재하는 방식은 구글에 도움을 받음.. 항상 풀고 나면 덜 어려워 보임 (다시 풀어볼 만함)

 

코드

#include <iostream>
#include <vector>
#include <set>
#include <string>
using namespace std;
bool visit[50] = { false, };

vector<int> v[10];
 
set<string> s;

void  dfs(int num, int N) 
{
	if (num == N) 
	{
		string tmepStr = "";
		for (int i = 0; i < 10; i++)
			if (visit[i] == 1)
			{
				tmepStr += to_string(i);
			}
		s.insert(tmepStr);
		return;
	}

	for (int j = 0; j < v[num].size(); j++) 
	{
		int cur = v[num][j];
		if (visit[cur] == 1) continue;
		visit[cur] = 1;
		dfs(num + 1, N);
		visit[cur] = 0;
	}
 
} 

int solution(vector<string> user_id, vector<string> banned_id)
{
	int answer = 0;
	for (int i = 0; i < banned_id.size(); i++)
	{
		for (int j = 0; j < user_id.size(); j++)
		{

			int cnt = 0;
			int starcnt = 0;
			if (banned_id[i].length() != user_id[j].length())
				continue;
			for (int w = 0; w < banned_id[i].length(); w++)
			{
			
				if (banned_id[i][w] == '*')
				{
					starcnt++;
					continue;
				}
				if (banned_id[i][w] != user_id[j][w])
				{
					break;
				}
				else if( banned_id[i][w] == user_id[j][w])
				{
					cnt++;
				}
			}
			if (user_id[j].length() - starcnt == cnt)
			{
				v[i].push_back(j);
				//visit[j] = true;
			}
		}
	}
	 dfs(0, banned_id.size());
	 answer = s.size();
	return answer;
}
int main()
{
	//solution({ "frodo","fradi","crodo","abc123","frodoc" }, { "fr*d*","abc1**" });
	solution({ "frodo","fradi","crodo","abc123","frodoc" }, { "fr*d*","*rodo","******","******"});
	return 0;
}