문제 링크

🤔 풀이 방법

풀이 방법: 순열 + Set을 이용.

1. 순열을 이용하는 이유

banned_id에 매칭되는 user_id 목록들을 찾아야되는데 user_id의 길이가 1이상 8이하이기에 brute force형식으로 진행해도 시간내에 통과가 되기에 순열을 이용한다.

2. Set을 사용하는 이유

순열을 이용해서 나오는 user_id의 값의 중복 제거를 위해서이다.
ex) user_id가 [frodo,crodo]일 경우, 만들 수 있는 순열은 [frodo, crodo], [crodo,frodo] 이다. 하지만, 두 개의 값들은 동일하다. !!

👉 소스 코드

class Solution {
    var set = mutableSetOf<MutableSet<String>>()
    fun solution(user_id: Array<String>, banned_id: Array<String>): Int {
        permutation(
            depth = 0,
            visited = BooleanArray(user_id.size),
            candidate = Array<String>(banned_id.size) { "" },
            banned_id = banned_id,
            user_id = user_id
        )
        return set.size
    }

    private fun permutation(
        depth: Int,
        visited: BooleanArray,
        user_id: Array<String>,
        candidate: Array<String>,
        banned_id: Array<String>
    ) {
        if (depth == banned_id.size) {
            if (matching(candidate, banned_id)) {
                
            }
            return
        }

        for (i in user_id.indices) {
            if (!visited[i]) {
                visited[i] = true
                permutation(
                    depth = depth + 1,
                    visited = visited,
                    user_id = user_id,
                    candidate = candidate.apply {
                        this[depth] = user_id[i]
                    },
                    banned_id = banned_id
                )
                visited[i] = false
            }
        }
    }


    private fun matching(candidate: Array<String>, banned_id: Array<String>): Boolean {
        for (i in candidate.indices) {
            val id = candidate[i]
            val bId = banned_id[i]

            if (id.length != bId.length)
                return false

            id.zip(bId) { c1, c2 ->
                if (c1 != c2) {
                    if (c2 != '*')
                        return false
                }
            }
        }
        
        set.add(candidate.toMutableSet())
        return true

    }
}