프로그래머스[programmers] - 불량사용자(Kotlin)[LV3]

문제

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

프로그래머스

 

문제 풀이

전형적인 백트래킹 문제이다.

우선 응모자아이디를 이용해서 조합을 만들고, 만들어진 조합의 크기가 불량 사용자 아이디 목록의 크기와 동일해질 경우 

매핑을 시작한다.

매핑은 다음과 같은 과정으로 이루어진다.

1. 후보 아이디 목록과 불량 사용자 아이디 목록은 1:1로 매칭한다.
2. 만약 길이가 다를 경우 매핑은 실패한다.
3. *을 제외한 글자가 다를 경우 매핑은 실패한다.

매핑이 성공했다면, 결과를 저장한다.

여기서 결과를 저장하는 과정에서 [A, B]와 [B, A]는 같기 때문에, 결과는 Set에 저장을 한다.

Lv3라고 해서 걱정을 했는데, 생각보다 쉬운 문제였다.

Set이라는 자료구조를 선택할수 있는 사고가 있다면, 쉽게 풀 수 있는 문제이다.

매핑을 하는 과정은 그렇게 어렵지 않다고 생각한다.

 

 

전체 코드

class Solution {

    private val idSet = mutableSetOf<MutableSet<String>>()
    private lateinit var visit : Array<Boolean>
    private val candidate = mutableListOf<String>()
    var limit = 0
    fun solution(user_id: Array<String>, banned_id: Array<String>): Int {
        var answer = 0
        limit = user_id.size
        visit=Array(limit){false}
        makeCombination(user_id,banned_id)
        return idSet.size
    }

    fun makeCombination(user_id : Array<String>, banned_id : Array<String>){
        if(candidate.size == banned_id.size){
            if(matchingId(user_id,banned_id)) idSet.add(candidate.toMutableSet())
            return
        }

        for(i in 0 until user_id.size){
            if(visit[i])
                continue
            candidate.add(user_id[i])
            visit[i]=true
            makeCombination(user_id,banned_id)
            visit[i]=false
            candidate.remove(user_id[i])

        }
    }
    fun matchingId(user_id : Array<String>,banned_id : Array<String>) : Boolean{
        for(i in 0 until banned_id.size){ //후보군들중에서. 순서를 해야하는구나..
            if(candidate[i].length != banned_id[i].length) //길이가 다를 경우
                return false
            for(j in 0 until candidate[i].length){
                if(banned_id[i][j]=='*')
                    continue
                if(banned_id[i][j]!=candidate[i][j])
                    return false
            }

        }
        return true
    }
}