3-6. 프로그래머스 - 불량 사용자

1. 관련 문제 🎯

문제 : 프로그래머스 불량 사용자 👿
난이도 : LEVEL 3

2. 문제 소개 🧩

1️⃣ 비정상적인 방법으로 당첨을 시도한 응모자들을 따로 모아 불량 사용자라는 이름으로 목록을 만들었다.

2️⃣ 이 때, 개인정보 보호을 위해 사용자 아이디 중 일부 문자를 '*' 문자로 가려서 전달했다.

• 가리고자 하는 문자 하나에 '*' 문자 하나를 사용하였고, 아이디 당 최소 하나 이상의 '*' 문자를 사용하였다.

3️⃣ 불량 사용자 목록에 매핑된 응모자 아이디를 제재 아이디라고 부르기로 했다.

4️⃣ 이벤트 응모자 아이디 목록이 담긴 배열 user_id와 불량 사용자 아이디 목록이 담긴 배열 banned_id가 주어질 때, 당첨에서 제외되어야 할 제재 아이디 목록은 몇가지 경우의 수가 가능한 지 구해야 한다.

---

예시
1) 이벤트에 응모한 전체 사용자 아이디 목록
응모자 아이디 = [frodo, fradi, crodo, abc123, frodoc]

2) 불량 사용자 아이디 목록
불량 사용자 = [fr*d*, abc1**]

☝️ 불량 사용자에 매핑되어 당첨에서 제외되어야 야 할 제재 아이디 목록

• 제재 아이디 = [frodo, abc123]
• 제재 아이디 = [fradi, abc123]

➡️ 따라서 총 2가지이다.

3. 문제 풀이 🖌️

먼저, 아래의 예시로 구체적인 문제 풀이를 구해보자!!

1️⃣ banned_id를 기준으로 user_id중에서 banned_id가 될 수 있는 id를 구한다.

• 따라서 구해보면, 아래의 파란색의 표로 나타낼 수 있다.
  

2️⃣ banned_id로 나올 수 있는 조합의 경우를 구한다.

이때, 고려해야 할 점은 2가지가 있다.

☝️ 첫번째로, [frodo, frodo, frodoc]처럼 이미 선택한 id가 반복될 수 없다는 점이다.

• 이를 해결하기 위해서, visited와 같이 방문여부를 체크하는 배열이나 map을 사용한다.
  ➡️ 이때, 조합에서 중복하지 않는 조합의 경우를 생각해볼 수 있다!
• 해당 문제에서는 map<string, bool> visited을 사용하여 방문여부를 체크했다.

✌️ 두번째로, [frodo, crodo, frodoc], [crodo, frodo, frodoc]은 순서가 다르지만 선택한 id가 동일하므로 동일한 경우의 수이다.

• 이를 고려하기 위해서, set<string> ans set 자료구조를 사용하여 중복뿐만 아니라 정렬을 동시에 해주었다.
• [frodo, crodo, frodoc], [crodo, frodo, frodoc] 배열을 set로 사용하면, 모두 [crodo, frodo, frodoc]으로 같은 배열로 된다.

4. 전체 코드 🔑

#include <string>
#include <vector>
#include <map>
#include <set>
using namespace std;

set<set<string>> answer;
map<string, bool> visited;
set<string> ans;
vector<vector<string>> valiable_banned_ids;

void permutation(int cnt){
    if(cnt == valiable_banned_ids.size()){
        answer.insert(ans);
        return;
    }
    for(int i=0; i<valiable_banned_ids[cnt].size(); i++){
        string x = valiable_banned_ids[cnt][i];
        if(!visited[x]){
            visited[x] = true;
            ans.insert(x);
            permutation(cnt+1);
            visited[x] = false;
            ans.erase(x);
        }
    }
}

int solution(vector<string> user_id, vector<string> banned_id) {

	//banned_id를 기준으로 user_id중에서 banned_id가 될 수 있는 id를 구한다.
    for(int i=0; i<banned_id.size(); i++){
        vector<string> banned_ids;
        for(int j=0; j<user_id.size(); j++){
            if(banned_id[i].size() != user_id[j].size()){
                continue;
            }
            bool is_banned_id = true;
            for(int k=0; k<banned_id[i].size(); k++){
                if(banned_id[i][k] == '*'){
                    continue;
                }
                if(banned_id[i][k] != user_id[j][k]){
                    is_banned_id = false;
                    break;
                }
            }
            if(is_banned_id){
                banned_ids.push_back(user_id[j]);
            }
        }
        valiable_banned_ids.push_back(banned_ids);
    }
    
    //banned_id로 나올 수 있는 조합의 경우를 구한다.
    permutation(0);
    
    return answer.size();
}

5. 결과 🏆