[LV3] 불량 사용자

1. 문제

1) 문제 링크

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

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

 

2) 설명

    user id 배열과 불량 사용자 id 배열이 주어진다.

불량 사용자 id는 중간중간 *(wild mask)가 들어갈 수 있다.(길이는 반드시 맞아야 한다)

이때 불량 사용자가 될 수 있는 user id들의 집합의 수를 구하면 된다.

 

2. 풀이

1) 알고리즘

    : set, bit연산

 

2) 풀이 설명

일단 user_id 배열이나 banned_id 배열이나 8개 이하라서 그냥 조합을 다 살펴보면서 세면 될 것 같았다.

이 조합의 수 세기를 재귀적으로 풀기 위해 전역변수로 my_user_id, my_banned_id, my_answer, id_set 들을 선언해주었다.

(매번 함수 인자로 넘기기 귀찮아서..)

그리고 user_id가 banned_id 에 해당하는지를 확인하는 is_matched함수도 하나 만들었다.(wild mask 때문에 새로 만들어줘야 했다.)

 

calculate_comb_num 함수는 banned_id의 index를 인자로 받아서 거기에 맞는 user_id들을 선택한 다음에  다음에 체크할 banned_id의 순번(banned_idx)와 해당 user_id를 선택했다는 사실(id_bit_check에 선택한 user_id의 index를 &연산)을 인자로 해서 자기 자신을 호출한다.

이 과정은 banned id를 다 셀 때까지 계속되고, 그때 구한 조합의 집합(id_bit_check)가 id_set에 없을 때 myAnswer 값을 1 증가시켜준다.(id_set에 있다는 말은 이전에 이미 카운팅했다는 말임으로)

 

3. 코드

// 풀이

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

using namespace std;

vector<string> my_user_id, my_banned_id;
int my_answer = 0;
set<int> id_set;

bool is_matched(string id, string form){
    //불량사용자 form에 id가 맞는지 확인하는 함수
    if(id.length() != form.length())
        return false;
    for(int i=0;i<id.length();i++){
        if(id[i] == '*' || form[i] == '*')
            continue;
        if(id[i] != form[i])
            return false;
    }
    return true;
}

void calculate_comb_num(int banned_id_idx, int id_bit_check){
    /*
        @banned_id_idx        = 다음에 택할 불량사용자 index
        @id_bit_check = bit로 표현한 불량사용자로 선택된 user 집합
    */
    if(banned_id_idx == my_banned_id.size()){ 
        //불량사용자를 다 배정했으면 진입
        if(id_set.find(id_bit_check) != id_set.end()){
            //이미 셌던 집합이면 return
            return;
        } 
        my_answer++; //조합 개수 증가
        id_set.insert(id_bit_check); //id_set에 추가
        return;
    }
    for(int i=0;i<my_user_id.size();i++){
        if(!(id_bit_check & (1 << i)) && is_matched(my_user_id[i], my_banned_id[banned_id_idx])){
            //불량 사용자로 선택했던 user가 아니면 + 불량사용자 조건에 해당하면...
            calculate_comb_num(banned_id_idx + 1, id_bit_check | (1 << i));
        }
    }
}

int solution(vector<string> user_id, vector<string> banned_id) {
    my_user_id = user_id;
    my_banned_id = banned_id;
    
    calculate_comb_num(0, 0);
    
    return my_answer;
}

 

 

4. 느낀점

문제에서 스네이크 표기법 써서 그냥 통일해서 쓰는데 언더바 치기 귀찮다...

카멜표기법이 게으른 나에게 더 맞는 것 같다..