https://school.programmers.co.kr/learn/courses/30/lessons/64064
유저들의 아이디인 user_id와 불량 사용자들의 아이디인 banned_id 배열이 주어진다.
와일드 카드가 사용된 banned_id의 각 문자열들에 각 user_id의 문자열들을 매칭하여 제재 아이디 목록을 구성하고, 이 케이스들의 개수를 구하는 문제이다.
첫 번째 예시에 대해서 ["frodo", "abc123"], ["fradi", "abc123"] 매칭 케이스 두개가 존재하므로 2를 반환한다.
두 번째 예시에 대해서 ["frodo", "crodo", "abc123"], ["frodo", "crodo", "frodoc"] 두 가지 케이스가 존재하므로 2를 반환한다.
frodo와 crodo의 순서와 관계없이 배열을 구성하는 목록이 동일한 경우 같은 것으로 여긴다 했음을 주의한다.
제한 사항은 다음과 같다.
- user_id와 banned_id의 길이는 1~8이다.
- user_id의 각 문자열들은 중복되지 않으며 소문자 or 숫자만 있다.
- banned_id의 각 문자열들은 *를 하나 이상 포함하며 같은 user_id를 연속으로 포함할 수 없다.
user_id 배열과 banned_id 배열이 크기가 1~8로 매우 작으므로 일일이 넣어보는 방식으로 풀었다.
구상한 방법은 다음과 같다
user_id: ["frodo", "fradi", "crodo", "abc123", "frodoc"]
banned_id: ["*rodo", "*rodo", "******"]
아이디들이 위와 같이 주어진 경우, 아래처럼 banned_id를 기준으로 매칭이 되는 user_id들을 추가한다.
"*rodo" - ["frodo", "crodo"]
"*rodo" - ["frodo", "crodo"]
"******" - ["abc123", "frodoc"]
그 다음 각 banned_id에 대해 user_id를 key로 사용하는 Map을 생성해 선택 여부를 체크하며 재귀로 케이스들을 골라낸다.
첫 번째 "*rodo"에서, "frodo"를 선택하고 map[frodo]에 true로 체크한다.
이후 두 번째 "*rodo"에서 frodo에 방문 체크가 되어있으므로 다음인 crodo에 방문 체크 후 넘어간다.
다음 "******"에서 abc123을 체크하고, 세 개를 모두 골랐으므로 케이스를 만들어낸다.
위처럼 순열? 방식으로 일일이 골라낸다면 주의해야 할 점이 중복 체크이다.
["frodo", "crodo", "abc123"]과 ["crodo", "frodo", "abc123"]은 같은 케이스로 취급한다고 하였다.
따라서 정답 체크용 Map을 하나 더 만들고 케이스를 만들어 낸 경우, 방문 체크에 사용된 map을 sorted맵으로 바꾼 후 key를 StringBuilder로 이어붙여 중복 체크를 한다.
["frodo", "crodo", "abc123"]의 케이스를 정렬 후 이어 붙이면 "abc123 crodo frodo"가 되고, 정렬 하였으므로 ["crodo", "frodo", "abc123"]도 동일하다.
이를 통해 중복 체크를 하였다.
class Solution {
fun solution(user_id: Array<String>, banned_id: Array<String>): Int {
val matches = Array(banned_id.size){ mutableListOf<String>()}
for(i in banned_id.indices){
for(user in user_id){
if(isMatched(banned_id[i], user)){
matches[i].add(user)
}
}
}
var answer = 0
val check = mutableMapOf<String, Boolean>()
comb(matches, 0, mutableMapOf()){
val str = StringBuilder()
for(key in it.keys){
if(it[key] == true){
str.append("$key ")
}
}
if(check[str.toString()] == null){
check[str.toString()] = true
answer++
}
}
return answer
}
fun isMatched(banned: String, user: String): Boolean{
if(banned.length != user.length) return false
for(i in banned.indices){
if(banned[i] != '*' && banned[i] != user[i]) return false
}
return true
}
fun comb(matches: Array<MutableList<String>>, idx: Int, visited: MutableMap<String, Boolean>, caseMade: (Map<String, Boolean>) -> Unit){
if(matches.size == idx){
caseMade(visited.toSortedMap())
return
}
val users = matches[idx]
for(user in users){
if(visited[user] == null || !visited[user]!!){
visited[user] = true
comb(matches, idx + 1, visited, caseMade)
visited[user] = false
}
}
}
}위에서 언급한 대로
- banned_id 기준 매칭이 되는 user_id 목록을 생성
- 방문 체크용 Map을 생성해 재귀 함수를 만들어 각 선택 케이스를 뽑아냄.
- 각 선택 케이스마다 방문 체크한 map을 정렬 후 문자열로 만들어 중복을 걸러냄.
