2019 카카오 개발자 겨울 인턴십 코딩테스트 - 불량 사용자

DFS 문제이다.

따로 알고리즘을 공부한 적이 없어서 필요한 개념이 있으면 원리만 익힌 뒤 나름대로 구현해 보고 있다.

Stack을 이용하는 방법도 있는 것 같은데 개인적으로 재귀가 가장 직관적으로 잘 풀려서 재귀를 이용했다.

 

다만 재귀를 이용할 경우 항상 Stack이 넘치는 것을 주의해야 한다.

이 문제의 경우 표본이 크지 않아서 문제가 없었으나

혹시 표본이 커질 경우 경우의 수를 좀 더 쳐내거나 꼬리재귀를 사용하는 방법도 고려해야 한다.

 

우선 각각의 banned_id에 해당될 수 있는 모든 유저를 각각의 리스트에 담아 matched_id를 만든다.

예를 들어 사용자 목록 : [철수, 영희, 철구, 미애, 은희] 가 있고 불량 사용자 : [철*, *구, *희] 가 있다면

철* -> 철수, 철구

*구 -> 철구

*희 -> 영희, 은희

가 각각의 경우에 해당되므로 가능한 모든 경우의 수는 [철수, 철구, 영희] 또는 [철수, 철구, 은희] 2가지이다.

 

이를 찾는 방법은 다음과 같다.

 

1) 2*1*2 가지의 모든 경우를 탐색한다 (DFS)

2) 다만 탐색 중간에 이전 원소와 중복되면 (예를 들어 철* -> 철구, *구 -> 철구 가 나온 경우) 탐색을 중단한다.

3) 마지막 깊이까지 모두 탐색된 경우 이제까지 조합된 유저 목록을 정렬하여 문자열로 합친 뒤 set에 넣어준다.

4) set의 사이즈를 구한다 (중복없이 가능한 모든 불량사용자 목록이므로)

 

 

fun solution(user_id: Array<String>, banned_id: Array<String>): Int {
        var answer = 0
        val matched_id = Array<MutableList<String>>(banned_id.size) { mutableListOf() }

        // 각각의 밴 id에 해당되는 id 들을 체크함
        banned_id.forEachIndexed { index, _banned_id ->
            val pattern = Pattern.compile(toRegexStr(_banned_id))
            user_id.forEach { _user_id ->
                val matcher = pattern.matcher(_user_id)
                if (matcher.matches()) {
                    matched_id[index].add(_user_id)
                }
            }
        }

        // DFS
        val lastDepth = matched_id.size-1 // 탐색의 마지막 깊이
        val resultSet = mutableSetOf<String>() // 중복여부를 체크하는 Set
        fun dfs(currentDepth: Int, beforeThis: List<String>) {
            if (currentDepth>lastDepth) { // 탐색이 완료되었다면 정렬한 뒤 문자열로 바꿔 Set 에 넣는다.
                beforeThis.sorted().joinToString(" ").let { resultSet.add(it) }
            } else {
                matched_id[currentDepth].forEach { // 이전 값이 중복되지 않을 경우 다음 깊이로 진행한다.
                    if (!beforeThis.contains(it)) dfs(currentDepth+1, beforeThis.toMutableList().apply { add(it) })
                }
            }
        }

        dfs(0, listOf())

        answer = resultSet.size
        return answer
    }
    fun toRegexStr(str: String): String {
        return str.map { char ->
            if (char == '*') '.' else char
        }.joinToString("")
    }