[프로그래머스] 2019 카카오 개발자 겨울 인턴십 불량 사용자 with Kotlin

문제

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

프로그래머스

 

풀이 과정

1. banned_id를 기준으로 가능한 user_id를 HashMap에 저장, key는 banned_id의 인덱스

2. HashMap을 바탕으로 DFS 탐색하여 가능한 조합 List에 저장

3. List에는 중복되는 조합도 있음으로 toSet()을 활용하여 중복 제거 후 크기 반환

 

코드

class Solution {
    fun solution(user_id: Array<String>, banned_id: Array<String>): Int {
        val hash = hashMapOf<Int, MutableList<String>>()
        
        // banned_id에 들어갈 수 있는 아이디 목록 hash에 저장
        banned_id.forEachIndexed{ key, id ->
            val length = id.length
            val index = mutableListOf<Int>()
            
            id.forEachIndexed{ i, it ->
                if(it == '*') index.add(i)
            }
            
            user_id.filter{it.length == length}.forEachIndexed{ id_index , filter ->
                var sb = StringBuilder(filter)
                
                for(i in index){
                    sb[i] = '*'
                }
                
                if(sb.toString() == id) hash.getOrPut(key){ mutableListOf() }.add(filter)
            }
        }
        
        // hash를 바탕으로 DFS 탐색
        dfs(hash, 0, mutableListOf<String>())
        
        // set으로 중복 제거 후 크기 반환
        return combination.toSet().size
    }
    
    // 가능한 아이디 조합 모음
    val combination = mutableListOf<MutableList<String>>()
    
    fun dfs(hash: HashMap<Int, MutableList<String>>, key: Int, save: MutableList<String>){
        if(key == hash.size){
            save.sort()
            combination.add(save)
            return
        }
        
        // hash key(banned_id의 인덱스) 순서대로
        hash.get(key)!!.forEach{
            val newSave = mutableListOf<String>()
            newSave.addAll(save)
            
            if(!newSave.contains(it)){
                newSave.add(it)
                dfs(hash, key+1, newSave)
            }
        }
    }
}