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

https://programmers.co.kr/learn/courses/30/lessons/64064

프로그래머스

아이디와 일부 문자가 *로 표기된 불량 아이디 목록이 주어졌을 때

불량 아이디 목록과 일치하는 아이디 셋의 종류가 몇 개인지를 출력하는 문제이다.

 

인풋사이즈가 정말 작기 때문에 그냥 2중 for문을 돌리면서 글자를 하나하나씩 검사해도 잘 풀린다.

=> 여기서 검사결과를 저장하기 위해 2차원 배열인 mapping_id 를 선언하였다. (banned_id 별로 가능한 id의 index를 저장)

 

따라서 이 문제의 진짜 키포인트는 불량 아이디 목록과 일치하는 아이디 셋의 종류를 순서, 중복없이 카운트 하는 것.

이건 count함수를 선언한 뒤, 재귀호출을 통해 해결하였다.

먼저 count 함수는 인자로 a, cnt를 받는데 a는 비트마스킹 값을 저장할 int형 변수이고 cnt는 mapping_id의 인덱스를 나타낸다.

count(0, 0)을 실행하면 cnt가 0이므로 mapping_id[0]의 원소를 하나씩 읽어서 비트 변경 후 count(a, 1)을 실행한다.

이 과정을 계속 재귀적으로 반복하다가 cnt가 mapping_id의 사이즈와 동일할 때 a값을 set에 넣어주고 함수를 종료한다.

여기서 굳이 a를 set에 넣어주는 이유는 중복값을 없애기 위해서이다.

 

count 함수 호출이 끝나면 set에는 가능한 모든 아이디의 조합이 순서, 중복없이 들어있으므로 set의 사이즈를 리턴하면 끝!

 

#include <string>
#include <vector>
#include <set>

using namespace std;

set<int> s;
vector<vector<int>> mapping_id;

void count(int a, int cnt) {
	if (cnt == mapping_id.size()) {
		s.insert(a);
		return;
	}

	for (int i : mapping_id[cnt]) {
		if (a & (1 << i)) continue;    // i번째 비트가 이미 1이면 패스
		else {
			int b = a | (1 << i);
			count(b, cnt + 1);
		}
	}
}

bool equals(const string &id, const string &banned) {
	if (id.length() != banned.length()) return 0;
	else {
		for (int i = 0; i < id.length(); i++) {
			if (banned[i] == '*') continue;
			else if (id[i] != banned[i]) return 0;
		}
	}
	return 1;
}

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

	for (int i = 0; i < banned_id.size(); i++) {
		for (int j = 0; j < user_id.size(); j++) {
			if (equals(user_id[j], banned_id[i])) {
				mapping_id[i].push_back(j);
			}
		}
	}

	count(0, 0);

	answer = s.size();

	return answer;
}