1. 문제 설명

불량 사용자

2. 문제 분석

가능한 조합을 숫자를 통해 표시, DFS로 백트래킹했다. 조합을 적절히 응용해서 풀자.

1. 불법 사용자 아이디를 통해 가능성이 있는 유저 아이디를 원소로 하는 이차원 배열을 만들자.
2. 중복 아이디가 없기 때문에 동일한 아이디는 서로 다른 불법 사용자 아이디가 될 수 없다. 집합을 통해 해당 아이디를 숫자로 표현하자
3. 불법 아이디 배열은 곧 해당 불법 아이디가 될 수 있는 정수로 표현된 이차원 리스트가 된다.
4. 전체 아이디는 집합을 통해 가지고 있기 때문에 조합 DFS 백트래킹을 통해 각 불법 아이디에서 가능한 아이디를 선택해 들고 오자. 중복 체크를 위해 집합으로 검사했다.

3. 나의 풀이

import Foundation

func solution(_ user_id:[String], _ banned_id:[String]) -> Int {
    var banLists = [[String]]()
    var banList = [String]()
    for ban in banned_id {
        banList = []
        for user in user_id {
            if isBannedId(user, ban) {
                banList.append(user)
            }
        }
        banLists.append(banList)
    }
    var banListSet = Set(banLists.flatMap{$0})
    var checked = Array(repeating: false, count: banListSet.count)
    var banDict = [String : Int]()
    var index = 0
    
    for ban in banListSet {
        banDict[ban] = index
        index += 1
    }
    
    var banListInt = [[Int]]()
    var tmp = [Int]()
    for banList in banLists {
        tmp = []
        for ban in banList {
            tmp.append(banDict[ban]!)
        }
        banListInt.append(tmp)
    }

    var totalSet = Set<String>()
    
    func DFS(_ banListIdx: Int, _ banCount: Int, _ id: [Int]) {
        if banCount == banListInt.count {
            let id = id.sorted()
            let banIdString = id.map{String($0)}.joined()
            totalSet.insert(banIdString)
            return
        }
        
        let banList = banListInt[banListIdx]
        
        for ban in banList {
            if !checked[ban] {
                checked[ban] = true
                DFS(banListIdx + 1, banCount + 1, id + [ban])
                checked[ban] = false
            }
        }
    }
    
    DFS(0, 0, [])
    
    return totalSet.count
}

func isBannedId(_ user: String, _ ban: String) -> Bool {
    if user.count != ban.count {
        return false
    }
    
    for idx in 0..<user.count {
        let userIdx = user.index(user.startIndex, offsetBy: idx)
        let userLetter = user[userIdx]
        let banIdx = ban.index(ban.startIndex, offsetBy: idx)
        let banLetter = ban[banIdx]
        
        if banLetter == "*" {
            continue
        } else if banLetter != userLetter {
            return false
        }
    }
    return true
}