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

이미지를 클릭하면 문제 사이트로 이동합니다.

---

 

 

💣 문제 이해

 

 

이벤트 응모자 아이디 목록이 담긴 배열 user_id와

 

불량 사용자 아이디 목록이 담긴 배열 banned_id가 매개변수로 주어질 때,

 

당첨에서 제외되어야 할 제재 아이디 목록은 몇 가지 경우의 수가 가능한 지 return 하도록 solution 함수를 완성해야 한다.

 

 

 

💭 풀이 과정

 

 

먼저 banned_id 와 길이가 동일한 user_id 를 찾고,

 

* 문자를 제외한 모든 문자가 동일하다면 같은 아이디라고 가정하고, 그 아이디의 인덱스를 저장한다.

 

각 banned_id 별로 가능한 user_id 후보가 한 개 이상이므로, 모든 조합의 수를 구하는 것이다.

 

동일한 조합의 중복이 가능하다면 곱하면 되지만, 중복을 허락하지 않으므로 체크해줘야 한다.

 

방법을 고민하다, 다른 풀이를 찾아보며 비트마스크 방식으로 중복을 제외한 가짓수를 체크했다.

 

 

 

작성 언어: C++

 

#include <iostream>
#include <vector>

using namespace std;

bool isVisited[1 << 8];

void bitMask(int index, int bnArrSize, int bitmask, vector<vector<int>> &vec) {
    if (index == bnArrSize) {
        isVisited[bitmask] = true;
        return;
    }
    
    for (auto num:vec[index]) {
        if (bitmask & (1 << num))   continue;   // 이미 표시한 아이디인 경우 패스
        bitMask(index + 1, bnArrSize, bitmask | (1 << num), vec);
    }
}


int solution(vector<string> user_id, vector<string> banned_id) {
    vector<vector<int>> eq_Index(banned_id.size());
    int answer = 0, check = 1;
    
    /*************************** 불량 아이디별로 일치하는 아이디 인덱스 저장 ***************************/
    
    for (int i = 0; i < banned_id.size(); ++i) {
        
        int bidLength = banned_id[i].length();    // 불량 사용자 아이디 길이
        
        for (int j = 0; j < user_id.size(); ++j) {
            int uidLength = user_id[j].length();  // 사용자 아이디 길이
            check = 1;
            
            if (uidLength != bidLength) {   // 아이디 길이가 같지 않으면 패스
                check = -1;
                continue;
            }else {                     // 아이디 길이가 같다면 문자 비교
                for (int k = 0; k < bidLength; ++k) {
                    if (banned_id[i][k] == '*') {   // *문자는 비교 패스
                        continue;
                    }else {
                        if (banned_id[i][k] != user_id[j][k]) { // 문자가 다르다면 check를 -1로 하고 문자 비교 종료
                            check = -1;
                            break;
                        }
                    }
                }
            }
            
            if (check == 1) {   // 두 아이디가 같다고 판단한 경우
                cout << "banned_id: " << banned_id[i] << "user_id: " << user_id[j] << '\n';
                eq_Index[i].push_back(j);
            }
            
        }
        
    }
    
    
    /*************************** 비트마스크로 존재하는 후보군 조사 ***************************/
    
    bitMask(0, banned_id.size(), 0, eq_Index);
    
    for (bool temp:isVisited) {
        if (temp == true)   answer++;
    }
    
    return answer;
}

 

 

 

🏆 배운 점

 

 

비트마스크를 사용하며 코드도 간결하고, 짧은 수행시간으로 연산할 수 있다는 장점을 경험했다.

 

이전에 책(알고리즘 문제 해결 전략)으로 비트마스크를 접한 적이 있는데,

 

실제 문제로 풀이하며 이해하고 다시 이론을 뒤적여보니 훨씬 이해가 잘된다.

 

역시 문제풀이 다다익선 인듯😎