2019 카카오 개발자 겨울 인턴십
제재 아이디를 통해서 만들 수 있는 사용자 아이디의 개수를 구하는 문제입니다.
제재 아이디를 통해서 가능한 아이디를 매칭해줍니다.
ex)
- userId -
abcde
aaaaa
aaaccc
aacde
- bannedId -
**cde
*****
- possibleBid -
**cde = {abcde, aacde}
***** = {abcde, aaaaa, aacde}
1. 재귀를 통해서 매칭된 아이디들을 조합이 가능한 형태로 만들어줍니다.
(아이디는 최대 8개이므로 비트를 사용해주었습니다 (2^8 = 256))
2. 재귀를 통해서 비트값을 쌓아가고 같은 비트가 들어오면 가지치기를 해주었습니다.
3. 제재하는 배열의 크기만큼 비트를 쌓았으면 해당 비트를 true로 만들어줍니다.
result[bit] = true;
4. 재귀가 끝난 후 result배열에서 true의 개수를 출력합니다.
#include <iostream>
#include <cstring>
#include <string>
#include <vector>
using namespace std;
bool result[1 << 8];
void makeCombination(int index, vector<vector<int> > pbid, int bit) {
if(index == pbid.size()){
result[bit] = true;
return;
}
for(int i=0; i<pbid[index].size(); ++i){
int inputBit = (1 << pbid[index][i]);
if(!(bit & inputBit)){
makeCombination(index+1, pbid, bit + (1 << pbid[index][i]));
}
}
}
bool checkPossible(string a, string b)
{
if(a.length() != b.length()){
return false;
}
for(int i=0; i<a.length(); ++i){
if(b[i] == '*'){
continue;
}
if(a[i] != b[i]){
return false;
}
}
return true;
}
int solution(vector<string> userId, vector<string> bannedId)
{
int answer = 0;
vector<vector<int> > possibleBid(bannedId.size());
vector<bool> check(8, false);
vector<string> checkId(8);
memset(result, false, sizeof(result));
for(int i=0; i<userId.size(); ++i){
for(int j=0; j<bannedId.size(); ++j){
if(checkPossible(userId[i], bannedId[j])){
possibleBid[j].push_back(i);
}
}
}
makeCombination(0, possibleBid, 0);
for(int i=0; i<256; ++i){
if(result[i]){
++answer;
}
}
return answer;
}
'알고리즘' 카테고리의 다른 글
[JavaScript] 프로그래머스 - 크레인 인형뽑기 게임 (0) | 2021.09.16 |
---|---|
[JavaScript] 프로그래머스 - 숫자 문자열과 영단어 (0) | 2021.09.14 |
[C++] 프로그래머스 - 셔틀버스 (0) | 2021.09.14 |
[C++] 프로그래머스 - 거리두기 확인하기 (0) | 2021.09.14 |
[C++] 프로그래머스 - 추석 트래픽 (0) | 2021.09.14 |