[C++/프로그래머스] 불량 사용자

문제

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

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

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

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

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

[제한사항]

• user_id 배열의 크기는 1 이상 8 이하입니다.
• user_id 배열 각 원소들의 값은 길이가 1 이상 8 이하인 문자열입니다.
  • 응모한 사용자 아이디들은 서로 중복되지 않습니다.
  • 응모한 사용자 아이디는 알파벳 소문자와 숫자로만으로 구성되어 있습니다.
• banned_id 배열의 크기는 1 이상 user_id 배열의 크기 이하입니다.
• banned_id 배열 각 원소들의 값은 길이가 1 이상 8 이하인 문자열입니다.
  • 불량 사용자 아이디는 알파벳 소문자와 숫자, 가리기 위한 문자 '*' 로만 이루어져 있습니다.
  • 불량 사용자 아이디는 '*' 문자를 하나 이상 포함하고 있습니다.
  • 불량 사용자 아이디 하나는 응모자 아이디 중 하나에 해당하고 같은 응모자 아이디가 중복해서 제재 아이디 목록에 들어가는 경우는 없습니다.
• 제재 아이디 목록들을 구했을 때 아이디들이 나열된 순서와 관계없이 아이디 목록의 내용이 동일하다면 같은 것으로 처리하여 하나로 세면 됩니다.

풀이

[재귀함수 이용]

user_id배열의 길이가 최대 8이기 때문에, 시간복잡도 면에서 충분한 여유가 있었다.

그래서 재귀함수로 구현했다.

재귀함수의 인자로 banned_id 배열에 대한 idx, bitmap(지금까지 뽑은 제재 아이디 목록)을 주었다.

 

[정규식]

banned_id들을 정규식형태로 만들기 위해 앞에 ^, 뒤에 $를 추가하고, *를 .으로 바꿔주었다. 

 

[비트맵]

뽑은 제재 아이디 목록을 나타내기 위해 비트맵을 사용했다.

0, 2번째 아이디가 뽑혔으면 -> 00000101(2)

 

처음에는, bool배열을 이용해서 제재 아이디안에 중복으로 들어가지 않도록 확인해주었다. 

그런데, 

user_id	banned_id
["frodo", "fradi", "crodo", "abc123", "frodoc"]	["*rodo", "*rodo", "******"]

위의 테스트 케이스에서

frodo, crodo, frodoc

crodo, frodo, frodoc 가 중복으로 세어지는 문제가 있었다 ㅜㅜ

banned_id에 같은 문자열이 두개가 있었기 때문이다.

 

이 점을 해결하기 위해, count를 세는 방식에서, set에 가능한 경우의 수를 모두 넣고 

마지막에 set의 크기를 return하는 방식을 사용하고자 했다.

 

그래서 bool vector를 set에 넣는 것 보다는 bitmap이 효율적일 것 같아 bitmap을 이용하는 방식으로 변경하였다. 

코드

전체 코드는 다음과 같다!

#include <string>
#include <vector>
#include <regex>
#include <algorithm>
#include <unordered_set>

using namespace std;

vector<string> user_ids;
vector<string> banned_ids;
unordered_set<int> bitmaps;

void recursive(int idx, int bitmap) {
    regex re(banned_ids[idx]);
    for (int i=0;i<user_ids.size();i++) {
        if (bitmap & (1<<i)) continue;
        if (regex_match(user_ids[i], re)) {
            bitmap += (1<<i);
            if (idx == banned_ids.size()-1) {
                bitmaps.insert(bitmap);
                continue;
            }
            recursive(idx+1, bitmap);
            bitmap -= (1<<i);
        }
    }
}
int solution(vector<string> user_id, vector<string> banned_id) {
    user_ids = user_id; banned_ids = banned_id; // 전역변수로 만들기
    // 정규식형태로 만들기 (^문자열.$)
    for (int i=0;i<banned_ids.size();i++) {
        banned_ids[i].insert(0,"^");
        replace(banned_ids[i].begin(), banned_ids[i].end(), '*', '.');
        banned_ids[i] += "$";
    }
    recursive(0,0);
    int answer = bitmaps.size();
    return answer;
}

결과