티스토리 뷰

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;
}

 

728x90
댓글
댓글쓰기 폼
공지사항