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

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

프로그래머스

🧐문제 설명

문제에서 banned_id라는 배열로 주어진 아이디의 목록을 분석해, 제재 아이디를 만드는 경우의 수를 구하는 문제이다.

⭐ 해결 과정

나는 이 문제를 중복 set을 이용해 풀었다.

예제 입력 2번을 이용해 설명해보자면, graph를 만들듯이 각 banned_id에 포함되는 user_id들을 찾아 이차원 배열 candidiates에 넣어주었다.

그 다음, 재귀함수를 사용해 candidates를 순회하면서 이 banned_id가 담당할 user_id를 골랐다. 이 때, 앞에서 고른 값은 뒤에서 선택하지 못하므로 find 함수를 이용해 같은 값이 중복으로 들어가는 경우를 제외해주었다.

selceted를 set 자료구조로 사용한 이유는 banned_id의 매핑이 0, 2, 3이든 2, 0, 3이든 같게 취급해줘야 하기 때문이다. 만약 selected를 vector<int> 자료구조로 사용하고 set<vector<int>>에 매핑되는 경우의 수를 넣어준다면 0 2 3, 0 2 4, 2 0 3, 2 0 4 총 네 개의 케이스가 생길 것이다. 따라서 selected의 자료구조를 set으로 지정하여 중복되는 조합을 제외하고 넣어주고, 똑같은 조합이 들어오는 경우를 한번 더 배제하기 위해 set 자료구조인 s에 넣어준다.

이렇게 완전 탐색으로 모든 banned_id에 대한 user_id를 매핑하였다면 set<set<int>> s; 에 insert해준다.

👻 소스 코드

#include <string>
#include <vector>
#include <algorithm>
#include <set>
#include <iostream>

using namespace std;

bool isCombined(string s, string id){
    if(s.length() != id.length()) return false; 
    for(int i = 0; i < s.length(); i++){
        if(s[i] == '*') continue; 
        if(s[i] != id[i]) return false; 
    }
    return true; 
}

void recursive(int index, vector<vector<int>> candidates, set<int> & selected, set<set<int>> & s){
    if(index == candidates.size()) {
        s.insert(selected); 
        return ;
    }
    for(int x : candidates[index]){
        if(selected.find(x) != selected.end()) continue; 
        selected.insert(x);
        recursive(index + 1, candidates, selected, s); 
        selected.erase(x); 
    }
}

int solution(vector<string> user_id, vector<string> banned_id) {
    int n = banned_id.size(), m = user_id.size(); 
    vector<vector<int>> candidates(n); 

    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++)
            if(isCombined(banned_id[i], user_id[j]))
                candidates[i].push_back(j); 
    }

    set<int> selected;
    set<set<int>> s; 
    recursive(0, candidates, selected, s); 

    return s.size();
}