[DAY88] Algorithm : Bad Users

가려진 불량 사용자 아이디 목록을 보고, 제재 대상이 될 수 있는 아이디 목록의 경우의 수를 구하는 문제다. $N$이 8 이하로 매우 작다는 점을 이용해 DFS(백트래킹)로 모든 경우를 탐색하고, set 자료구조를 활용해 중복된 목록을 제거하는 것이 핵심이다.

---

❓ 문제 분석

• 목표: banned_id 패턴에 매칭되는 user_id들의 조합 중, 서로 다른 목록의 개수 구하기.
• 제약 조건: user_id 배열의 크기가 최대 8이다.
  • $N$이 매우 작으므로 효율성보다는 정확한 완전 탐색이 요구된다.
  • 시간 복잡도는 최대 $8!$ 정도라 충분히 가능하다.
• 핵심 키워드: "와일드카드(*)", "순서 무관", "중복 제외".

---

💡 풀이 설계

1. 문자열 매칭 판별 (Helper Function)

• 가장 먼저 user_id와 banned_id가 매칭되는지 확인하는 함수 isMatch가 필요하다.
• 길이가 다르면 false, 문자가 다르더라도 banned_id가 *이면 true로 처리한다.

2. DFS와 백트래킹 (Backtracking)

• banned_id의 인덱스를 하나씩 늘려가며 매칭되는 user_id를 찾는다.
• 이미 선택된 유저는 다시 선택하면 안 되므로 visited 배열을 사용한다.
• 백트래킹 핵심:
  1. visited[i] = true (선택)
  2. dfs(index + 1) (다음 단계로 이동)
  3. visited[i] = false (돌아와서 선택 해제 $\rightarrow$ 그래야 다음 경로에서 이 유저를 쓸 수 있음)

3. 중복 제거 (Set of Sets)

• 문제에서 "순서와 상관없이 내용이 같으면 같은 것"이라 했다.
• set<string>: 하나의 목록 내에서 아이디들을 자동 정렬해 순서를 무시한다. (장바구니)
• set<set<string>>: 완성된 목록들 사이의 중복을 제거한다. (영수증 모음)

---

💻 코드 구현

#include <string>
#include <vector>
#include <set>

using namespace std;

// 전역 변수 선언
vector<bool> visited;
set<set<string>> results;

// 문자열 매칭 확인 함수
bool isMatch(const string& user, const string& banned) {
    if (user.length() != banned.length()) return false;
    for (int i = 0; i < user.length(); ++i) {
        if (banned[i] == '*') continue;
        if (user[i] != banned[i]) return false;
    }
    return true;
}

// DFS (백트래킹) 함수
void dfs(int index, const vector<string>& user_id, const vector<string>& banned_id) {
    // 모든 불량 아이디에 대한 짝을 다 찾았을 때 종료
    if (index == banned_id.size()) {
        set<string> temp_result;
        // visited가 true인 유저들만 모아서 하나의 세트로 만듦
        for (int i = 0; i < user_id.size(); ++i) {
            if (visited[i]) {
                temp_result.insert(user_id[i]);
            }
        }
        // 완성된 세트를 전역변수 results에 넣음
        results.insert(temp_result);
        return;
    }

    // user_id 전체를 돌며 매칭 시도
    for (int i = 0; i < user_id.size(); ++i) {
        // 아직 방문하지 않았고, 매칭이 된다면?
        if (visited[i] == false && isMatch(user_id[i], banned_id[index]) == true) {
            visited[i] = true;        // 체크
            dfs(index + 1, user_id, banned_id); // 재귀
            visited[i] = false;       // 체크 해제 : 백트래킹
        }
    }
}

int solution(vector<string> user_id, vector<string> banned_id) {
    results.clear(); // 전역 변수 초기화 후 사용
    visited.assign(user_id.size(), false); // user_id 크기, false 초기화

    // DFS 시작
    dfs(0, user_id, banned_id);

    // 결과 크기 반환
    return results.size();
}

---

🐛 시행착오 및 디버깅

• 문제점 1: set<set<string>> 자료구조가 처음엔 이해하기 어려웠다.
  • 해결: 안쪽 set은 순서 무시용, 바깥쪽 set은 중복 목록 제거용이라는 것을 이해하고 적용했다.
• 문제점 2: DFS 함수 인자로 result 세트를 계속 들고 다니려니 코드가 복잡해졌다.
  • 해결: 그냥 visited 배열만 잘 관리하고, 마지막 종료 조건에서 visited가 true인 애들만 싹 긁어모으는 방식으로 최적화했다.
• 새로 배운 것: vector.assign(크기, 값) 함수. 벡터를 초기화하고 값을 채우는 데 아주 유용하다.

---

✅ 오늘의 회고

항목	내용
유형	DFS, Backtracking (완전 탐색)
체감 난이도	상 (자료구조 활용과 재귀 설계가 까다로움)
복잡도	시간: $O(N!)$, 공간: $O(N)$
새로 배운 것	visited.assign() 사용법, set을 이용한 조합 중복 제거