프로그래머스 Lv3 불량 사용자

문제

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

풀이

• DFS로 각 banId에 알맞은 아이디를 찾아 리스트로 채우고, 다 찼을경우 ans++

• 단 String으로 된 List를 Set으로 구성해 순서에 상관없이 중복인 경우 체크 해제, 이를 위해 체크할때 내부 리스트를 sorted로 정렬해서 비교한다.

코드

class Solution {
    lateinit var visit : BooleanArray
    var ans = 0
    lateinit var userList : Array<String>
    lateinit var banList : Array<String>
    var list = mutableListOf<String>()
    var set = HashSet<List<String>>()
    fun solution(user_id: Array<String>, banned_id: Array<String>): Int {
        userList = user_id
        banList = banned_id
        visit = BooleanArray(userList.size){false}
        dfs(0)
        return ans
    }
    
    fun dfs(depth : Int){
        if(depth==banList.size){
            if(!set.contains(list.sorted())){
                set.add(list.sorted())
                ans++
            }
            return
        }
        
        for(i in 0 until userList.size){
            if(check(userList[i],banList[depth])&&!visit[i]){
                list.add(userList[i])
                visit[i] = true
                dfs(depth+1)
                visit[i] = false
                list.removeLast()
            } 
        }
    }
    
    fun check(userName : String, banName : String) : Boolean{
        if(userName.length!=banName.length){
            return false
        }
        for(i in userName.indices){
           if(userName[i]!=banName[i]&&banName[i]!='*'){
               return false
           }   
        }
        return true
    }
}