풀이 방법: 순열 + Set을 이용.
banned_id에 매칭되는 user_id 목록들을 찾아야되는데 user_id의 길이가 1이상 8이하이기에 brute force형식으로 진행해도 시간내에 통과가 되기에 순열을 이용한다.
순열을 이용해서 나오는 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
}
}