[Algorithm] 불량 사용자

[hwangJi-dev]

💬 문제

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

💬 Idea

1. 불량 사용자 id에 해당하는 사용자 id의 인덱스를 저장할 수 있도록 dictionary를 만들고, 반복문을 돌면서 dictionary에 값을 채운다.

   • [”frd”: [”frodo”, “fradi”], “rodo”: [”frodo”, ”crodo”], “*****”: [
     abc123”, “frodoc”]] 를 떠올리며 추후에 dfs를 수행할 때 편리하도록 실제 구현시에는 사용자 id의 인덱스값을 저장한다.

     ⇒ [”frd”: Set([0, 1]), “rodo”: Set([0, 2]), “*****”: Set([3, 4])]

2. dfs를 수행하며 불량 제재 아이디와 사용자 아이디를 맵핑한 쌍을 만든다.

   • dfs를 활용해야겠다고 떠올리면서, **dfs의 깊이(=depth)**를 banned_id 배열의 index로 응용하였다.
     • 즉, banned_id = ["frd", "abc1**"] 의 경우
       • depth가 0일 때 → frd에 해당하는 user_id가 결정되고
       • depth가 1일 때 → abc1** 에 해당하는 user_id가 결정된다.
       • 이렇게 depth가 깊어지면서 banned_id에 해당하는 유저의 id가 하나씩 결정되므로 depth의 최종 깊이가 되었을 때 하나의 제재 아이디 목록(bannedCase) 쌍이 생긴다.

   < dfs 설계 >

   • visited: user_id의 방문 여부(=현재 쌍에 포함되었는지)를 저장하는 visited 배열이다.
   • banIdx : 불량 아이디 목록의 index로서, dfs의 깊이를 뜻한다.
   • userIdx: 유저 아이디의 인덱스이다. visited 여부를 파악하고, 제재 아이디 쌍을 만드는데 사용된다.
   • bannedCase: 제재 아이디 쌍이 저장되는 Set형 배열이다.
   1. 현재 userIdx가 방문되지 않았다면, 현재 userIdx를 방문처리하고, bannedCase에 현재 user_id를 저장한다.
   2. 이후 다음 깊이가 존재한다면 (banIdx + 1가 banned_id의 개수보다 작다면)
      1. 다음 깊이에 해당하는 제재 id 후보들을 차례로 돌며 dfs를 수행한다.
   3. 제재 아이디 쌍의 개수가 깊이와 같아졌다면 제재 아이디 쌍을 저장하는 bannedCases에 해당 쌍을 저장하고 함수를 종료한다.

3. “제재 아이디 목록들을 구했을 때 아이디들이 나열된 순서와 관계없이 아이디 목록의 내용이 동일하다면 같은 것으로 처리하여 하나로 세면 됩니다” 라는 조건을 해결하기 위해서 Set<Set> 자료구조를 사용해주었다.

   1. 해당 조건을 처리하기 위해 처음에는 bannedCases를 Set<[String]> 으로 디자인하여 하나의 제재 아이디 목록(bannedCase)이 만들어지면 해당 배열을 정렬하여 bannedCases에 insert해주었다.

   하지만 해당 작업이 시간초과를 유발한다는 것을 깨닫고 bannedCases 자체를 Set<Set> 자료구조로 바꿔 구현해주었다. → case3번 시간초과가 떴었는데, 해당 방법으로 해결할 수 있었다. 😊

💬 풀이

import Foundation

func solution(_ user_id:[String], _ banned_id:[String]) -> Int {
    var banUserDict: [String: Set<Int>] = [:]
    var bannedCases: Set<Set<String>> = []

    for b in banned_id {
        if banUserDict[b] == nil {
            banUserDict[b] = []
        }

        for (udx, u) in user_id.enumerated() {
            if checkBanId(u, b) {
                banUserDict[b]?.insert(udx)
            }
        }
    }
    
    // dfs 수행 재귀함수
    func dfs(_ banIdx: Int, _ userIdx: Int, _ bannedCase: Set<String>, _ visited: [Bool]) {
        var bannedCase = bannedCase
        var visited = visited

        if !visited[userIdx] {
            visited[userIdx] = true
            bannedCase.insert(user_id[userIdx])
            if banIdx + 1 < banned_id.count {
                for i in banUserDict[banned_id[banIdx + 1]]! {
                    dfs(banIdx + 1, i, bannedCase, visited)
                }
            }
        }

        if bannedCase.count == banned_id.count {
            bannedCases.insert(bannedCase)
            return
        }
    }

    let visited = Array(repeating: false, count: user_id.count)
    
    for i in banUserDict[banned_id[0]]! {
        // 깊이 0부터 dfs 수행
        dfs(0, i, [], visited)
    }

    return bannedCases.count
}

// MARK: - 제한당한 id인지 확인하고 제한여부를 리턴하는 메서드
func checkBanId(_ user_id: String, _ banned_id: String) -> Bool {
    if banned_id.count != user_id.count { return false }

    let userID = Array(user_id)
    for (idx, i) in banned_id.enumerated() {
        if i != "*" && i != userID[idx] { return false }
    }

    return true
}

제출 후 해당 문제는 dfs가 중점이라기보단, HashSet을 잘 응용하여 문제를 푸는 능력이 요구되었던 것이라는 생각이 들어서 순열(permutation)을 이용하여 해당 문제를 한번 더 풀이해보았다 !

💬 Idea

순열은 조합과 달리, index 정보에 따라 다른 조합을 만들어내므로 해당 문제에 순열이 적합하다는 생각이 들었다.

1. banned_id.count 크기의 순열을 생성하여 perm에 저장한다.

2. 이후 perm을 돌면서 perm의 원소의 index와 banned_id의 index를 맵핑하여 checkBanId를 수행한다.

   • perm = [["frodo", "fradi"], ["frodo", "crodo"], ["frodo", "abc123"], ["frodo", "frodoc"], ["fradi", "frodo"], ["fradi", "crodo"], ["fradi", "abc123"], ["fradi", "frodoc"], ["crodo", "frodo"], ["crodo", "fradi"], ["crodo", "abc123"], ["crodo", "frodoc"], ["abc123", "frodo"], ["abc123", "fradi"], ["abc123", "crodo"], ["abc123", "frodoc"], ["frodoc", "frodo"], ["frodoc", "fradi"], ["frodoc", "crodo"], ["frodoc", "abc123"]]
   • banned_id = [”frd”, “abc1**”]

   perm[0]인 [”frodo”, “fradi”] 를 예로 들어보자. (perm[0]을 p로 지칭하겠다.)

   p[0] = “frodo” 와 banned_id[0] = ”frd” 를 맵핑하여 checkBanId를 수행한다.

3. p의 모든 원소가 banned_id와 맵핑된다면 해당 조합은 제재 아이디 목록에 해당됨을 뜻하므로 bannedCases에 넣어준다.

4. bannedCases의 개수를 리턴한다.

💬 풀이

import Foundation

func solution(_ user_id:[String], _ banned_id:[String]) -> Int {
    var bannedCases: Set<Set<String>> = []
    let perm = permutation_(user_id, banned_id.count)

    for p in perm {
        var isValid = true
        for (idx, i) in p.enumerated() {
            if !checkBanId(i, banned_id[idx]) {
                isValid = false
            }
        }

        if isValid {
            bannedCases.insert(Set(p))
        }
    }

    return bannedCases.count
}

// MARK: - 순열 메서드
func permutation_(_ array: [String], _ n: Int) -> [[String]] {
    var result = [[String]]()
    if array.count < n { return result }

    var visited = Array(repeating: false, count: array.count)

    func cycle(_ now: [String]) {
        if now.count == n {
            result.append(now)
            return
        }

        for i in 0..<array.count {
            if visited[i] {
                continue
            } else {
                visited[i] = true
                cycle(now + [array[i]])
                visited[i] = false
            }
        }
    }

    cycle([])

    return result
}

// MARK: - 제한당한 id인지 확인하고 제한여부를 리턴하는 메서드
func checkBanId(_ user_id: String, _ banned_id: String) -> Bool {
    if banned_id.count != user_id.count { return false }

    let userID = Array(user_id)
    for (idx, i) in banned_id.enumerated() {
        if i != "*" && i != userID[idx] { return false }
    }

    return true
}

이렇게 불량 사용자 문제를 dfs로 풀어보고, 순열을 이용해서도 풀어보았다.

풀고 나서 살펴보니 두 가지 방법 중 어느 것을 사용하여 푸는지는 중요하지 않았던 것 같다.

HashSet 자료구조를 알고, 활용할 줄 안다면 해당 문제를 어떤 방법으로든 풀 수 있기 때문이다!

그렇지만 시간 복잡도 측면에서 불필요한 비교를 줄이는 dfs 방법이 훨씬 더 좋은 효율을 가지기 때문에 더 좋은 풀이가 아닐까 생각이 들었다.