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

문제 링크: programmers.co.kr/learn/courses/30/lessons/64064

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

1. 주의할 점

- 불량사용자와 매칭된 사용자는 탐색할 수 없어야 한다

- 예제 2번과 같이 순서가 같지만 사용자는 같으므로 순열이 아닌 조합이다

 

2. 구현

- 불량사용자와 매칭된 사용자들이 오름차순으로 정렬하여 Set에 저장하여 조합의 수를 구하도록 한다

- DFS(idx)를 통하여 idx번째 불량사용자와 매칭되는 i번째 사용자를 구한다

- 사용자와 매칭되려면, 이미 선택된 사용자가 아니여야하며 불량사용자와 일반 사용자의 아이디 길이가 같아야 한다

- 위의 조건을 만족한다면, 문자 1개씩 비교하며 가능한지 판단한다. 가능하면 Check[] 값을 True로 설정하여 i번째 사용자가 이미 매칭됐다는 것을 나타낸다.

- 모든 불량 사용자들이 매칭되었다면, 이에 맞게 선택된 사용자들의 번호를 순서대로 Str에 담고 Set에 넣는다

- Set을 통해 순열->조합으로 분리가 가능하므로 Set의 크기만큼 반환한다

#include <string>
#include <vector>
#include <iostream>
#include <set>
using namespace std;
set<string> s;
bool check[8]={false,};
int len;
vector<string> bi,ui;

void dfs(int idx){
    if(idx==len){
        string str="";
        for(int i=0;i<ui.size();i++){
            if(check[i]) str+=(i+'0');            
        }
        s.insert(str);
        return;
    }
    for(int i=0;i<ui.size();i++){
        if(check[i]) continue;
        string su = ui[i];
        string sb = bi[idx];
        if(su.size()!=sb.size()) continue;
        bool avail=true;
        for(int k=0;k<su.size();k++){
            if(sb[k]=='*') continue;
            if(sb[k]!=su[k]){
                avail=false;
                break;
            }
        }
        if(avail){
            check[i]=true;
            dfs(idx+1);
            check[i]=false;
        }
    }
}

int solution(vector<string> user_id, vector<string> banned_id) {
    int answer = 0;
    len = banned_id.size();
    bi = banned_id;
    ui = user_id;
    
    dfs(0);
    return answer = s.size();
}