Programmers 64064 불량 사용자

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

프로그래머스

 

 

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

using namespace std;

// ✅ 1️ `banned_id` 패턴과 `user_id`가 매칭되는지 확인하는 함수
bool isMatch(string user, string banned) 
{
    if (user.size() != banned.size()) return false; // 길이가 다르면 불가능
    for (int i = 0; i < user.size(); i++) 
    {
        if (banned[i] != '*' && user[i] != banned[i]) 
        {
            return false; // '*'가 아닌 문자가 다르면 매칭 실패
        }
    }
    return true; // 패턴과 일치함
}

// ✅ 2️ 각 `banned_id`에 매칭될 수 있는 `user_id` 리스트 구성
vector<vector<string>> getMatchingList(vector<string>& user_id, vector<string>& banned_id) 
{
    vector<vector<string>> matching(banned_id.size());

    for (int i = 0; i < banned_id.size(); i++) 
    {
        for (string user : user_id) 
        {
            if (isMatch(user, banned_id[i])) 
            {
                matching[i].push_back(user); // 매칭되는 유저 저장
            }
        }
    }

    return matching;
}

// ✅ 3️ 백트래킹을 사용하여 가능한 모든 제재 조합을 찾음
void findCombinations(vector<vector<string>>& matching, vector<string>& chosen, set<set<string>>& results, int depth) 
{
    if (depth == matching.size()) 
    {
        set<string> temp(chosen.begin(), chosen.end());
        results.insert(temp); // 중복된 조합을 방지
        return;
    }

    for (string user : matching[depth]) 
    {
        if (find(chosen.begin(), chosen.end(), user) == chosen.end()) 
        { // 중복 방지
            chosen.push_back(user);
            findCombinations(matching, chosen, results, depth + 1);
            chosen.pop_back(); // 백트래킹
        }
    }
}

// ✅ 4️ `solution()` 함수: 전체 로직을 수행하는 메인 함수
int solution(vector<string> user_id, vector<string> banned_id) 
{
    vector<vector<string>> matching = getMatchingList(user_id, banned_id);
    set<set<string>> results; // 중복 없는 조합 저장
    vector<string> chosen;

    findCombinations(matching, chosen, results, 0);

    return results.size(); // 가능한 제재 아이디 조합의 개수
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    //vector<string> user_id;
    
    string id;
    int n;
    int m;
    cin >> n>>m;
    vector<string> user_id(n);
    vector<string> banned_id(m);
    for (int i = 0; i < n; i++)
    {
        cin>>user_id[i];
    }
    //for (auto a : user_id) cout << a << " ";
    for (int i = 0; i < m; i++)
    {
        cin >> banned_id[i];
    }
    //for (auto a : banned_id) cout << a << " ";

    cout << solution(user_id, banned_id) << '\n';


    return 0;
}

📌 C++ 코드 상세 설명

불량 사용자 목록(banned_id)과 user_id 리스트를 비교하여,
가능한 모든 조합을 찾고 중복을 방지하면서 경우의 수를 구하는 문제를 해결
주요 알고리즘은 백트래킹(Backtracking)과 set을 활용한 중복 제거

---

✅ 코드 전체 개요

1. 입력 받기 (main)
   • user_id와 banned_id를 입력받음.
2. 불량 사용자 패턴(banned_id)과 user_id 비교 (isMatch)
   • *이 포함된 banned_id가 user_id와 일치하는지 검사.
3. 각 banned_id에 대해 가능한 user_id 리스트 구성 (getMatchingList)
   • banned_id 하나당 user_id들 중 가능한 매칭된 ID 리스트를 저장.
4. 백트래킹을 이용하여 모든 조합 탐색 (findCombinations)
   • 각 banned_id에 대해 user_id를 하나씩 선택하여 경우의 수를 생성.
   • 중복된 경우를 제거하기 위해 set<set<string>> 사용.
5. 가능한 경우의 수 출력 (solution)
   • 백트래킹을 통해 찾은 중복 없는 조합 개수를 반환.

---

📌 1️⃣ main() 함수: 입력 처리

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int n, m;
    cin >> n >> m; // 사용자 수와 불량 사용자 수 입력받기
    
    vector<string> user_id(n);
    vector<string> banned_id(m);

    for (int i = 0; i < n; i++) {
        cin >> user_id[i];  // 사용자 ID 입력
    }

    for (int i = 0; i < m; i++) {
        cin >> banned_id[i];  // 불량 사용자 패턴 입력
    }

    // 결과 출력
    cout << solution(user_id, banned_id) << '\n';

    return 0;
}

🔹 입력 예시

5 2
frodo fradi crodo abc123 frodoc
fr*d* abc1**

🔹 입력된 벡터 상태

user_id = { "frodo", "fradi", "crodo", "abc123", "frodoc" }
banned_id = { "fr*d*", "abc1**" }

---

📌 2️⃣ isMatch() 함수: banned_id와 user_id 비교

bool isMatch(string user, string banned) {
    if (user.size() != banned.size()) return false; // 길이가 다르면 불가능
    for (int i = 0; i < user.size(); i++) {
        if (banned[i] != '*' && user[i] != banned[i]) {
            return false; // '*'가 아닌 문자가 다르면 매칭 실패
        }
    }
    return true; // 패턴과 일치함
}

🔹 예제 실행

isMatch("frodo", "fr*d*");   // true  (frodo → fr*d*)
isMatch("crodo", "fr*d*");   // true  (crodo → fr*d*)
isMatch("abc123", "abc1**"); // true  (abc123 → abc1**)
isMatch("frodoc", "fr*d*");  // false (frodoc ≠ fr*d*)

---

📌 3️⃣ getMatchingList() 함수: 각 banned_id에 대해 가능한 user_id 매칭 찾기

vector<vector<string>> getMatchingList(vector<string>& user_id, vector<string>& banned_id) 
{
    vector<vector<string>> matching(banned_id.size());

    for (int i = 0; i < banned_id.size(); i++) {
        for (string user : user_id) {
            if (isMatch(user, banned_id[i])) {
                matching[i].push_back(user); // 매칭되는 유저 저장
            }
        }
    }

    return matching;
}

🔹 예제 실행 결과

banned_id = { "fr*d*", "abc1**" }
user_id = { "frodo", "fradi", "crodo", "abc123", "frodoc" }

matching = {
  { "frodo", "crodo" },  // "fr*d*"에 매칭되는 user_id들
  { "abc123" }           // "abc1**"에 매칭되는 user_id들
}

---

📌 4️⃣ findCombinations() 함수: 백트래킹을 사용하여 가능한 모든 조합 찾기

void findCombinations(vector<vector<string>>& matching, vector<string>& chosen, set<set<string>>& results, int depth) {
    if (depth == matching.size()) {
        set<string> temp(chosen.begin(), chosen.end());
        results.insert(temp); // 중복된 조합을 방지
        return;
    }

    for (string user : matching[depth]) {
        if (find(chosen.begin(), chosen.end(), user) == chosen.end()) { // 중복 방지
            chosen.push_back(user);
            findCombinations(matching, chosen, results, depth + 1);
            chosen.pop_back(); // 백트래킹
        }
    }
}

🔹 백트래킹 탐색 과정

1. "fr*d*"에 가능한 ID → { "frodo", "crodo" }
2. "abc1**"에 가능한 ID → { "abc123" }

가능한 조합:
  { "frodo", "abc123" }
  { "crodo", "abc123" }

---

📌 5️⃣ solution() 함수: 전체 실행

int solution(vector<string> user_id, vector<string> banned_id) 
{
    vector<vector<string>> matching = getMatchingList(user_id, banned_id);
    set<set<string>> results; // 중복 없는 조합 저장
    vector<string> chosen;

    findCombinations(matching, chosen, results, 0);

    return results.size(); // 가능한 제재 아이디 조합의 개수
}

🔹 최종 출력

2

---

📌 실행 흐름 요약

1. 입력된 user_id와 banned_id를 처리
2. 각 banned_id에 대해 가능한 user_id를 리스트화
3. 백트래킹을 사용해 가능한 모든 경우 탐색
4. 중복된 경우를 set을 사용해 방지
5. 가능한 경우의 수 출력

---

⏳ 시간 복잡도 분석

• 매칭 리스트 생성 → O(N * M * L) (N=8, M=8, L=8이라 충분히 빠름)
• 백트래킹 탐색 → O(B!) (최대 8! = 40,320이므로 탐색 가능)
• 전체 시간 복잡도 → O(8!) (순열보다 빠름!)

---

🔥 결론

✅ 불량 사용자 패턴과 user_id 매칭 함수 구현
✅ 가능한 매칭 리스트 구성 (vector<vector<string>>)
✅ 백트래킹을 활용하여 모든 조합 탐색
✅ set을 활용해 중복된 조합 방지
✅ 최적의 O(8!) 풀이로 해결 가능!