[프로그래머스] 2019 카카오 개발자 겨울 인턴십 - 불량 사용자, C++

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

프로그래머스

본 문제는 불량 사용자 목록 중 한개를 선택하여 user_id와 일치하는 것을 찾는 문제다. 일치하는 user_id가 있을 경우에만 다음 순서로 넘어간다.

#include <string>
#include <vector>
#include <algorithm>
#include <set>
 
using namespace std;
 
bool chk[8];
set<string> s;
 
void cal(int index, string tmp, vector<string> user_id, vector<string> banned_id) {
    // 불량 사용자를 모두 찾았을 경우
    if (index == banned_id.size()) {
        // 중복 방지를 위한 정렬과 set
        sort(tmp.begin(), tmp.end());
        s.insert(tmp);
        return;
    }
    
    for (int i = 0; i < user_id.size(); i++) {
        // 길이가 다르거나 이미 다른 banned_id에 의해 차단된 경우 통과
        if (user_id[i].size() != banned_id[index].size() || chk[i]) continue;
        
        bool flag = false;
        
        for (int j = 0; j < banned_id[index].size(); j++) {
            // * 인 경우 통과
            if (banned_id[index][j] == '*') continue;
            
            // 글자가 다를 경우 반복문 끝
            if (user_id[i][j] != banned_id[index][j]) {
                flag = true;
                break;
            }
        }
        
        // 글자가 같을 경우
        if (!flag) {
            chk[i] = true;
            
            // 다음으로
            cal(index+1, tmp + to_string(i), user_id, banned_id);
            
            // 다른 banned_id로 차단 가능한 경우를 위해
            chk[i] = false;
        }
    }
}
 
int solution(vector<string> user_id, vector<string> banned_id) {
    cal(0, "", user_id, banned_id);
    return s.size();
}