[Swift] 불량 사용자 문제 풀이 [Programmers - Level3 (2019 카카오 개발자 겨울 인턴십)]

안녕하세요 보라봉입니다 :)

요즘 문제를 풀면서 이전보다 다른 풀이를 참고하는 일이 적어졌다는 걸 느꼈습니다! 아주 조금은 발전한 것 같다는 생각이 들었고, 그러면서 블로그에 저만의 알고리즘 풀이를 올리는 빈도가 늘게 된 것 같아요. 특히 프로그래머스 레벨2를 풀기 시작하면서는 이렇게 푸는게 맞나 고민하는 시간도 많았고, 1시간이 지나도 끙끙대면서 결국 다른 분의 풀이를 참고해서 문제를 해결하는 경우가 많았습니다. 그러면서 자신감도 조금씩 사라졌었는데요.. 알고리즘을 계속 공부하고 또 도전하면서, 점점 높은 레벨의 문제를 도전하고 풀어보면서 제 온전한 힘으로 문제를 풀게 되는 빈도도 늘어나는 것 같슴니다...! 😂 (그렇지만 아직도 어려운 알고리즘의 길..)

이 재미와 희열감 때문에 개발공부가 즐거웠고 개발을 좋아하게 되었었는데.. 요즘 공부를 하면서 잊었던 열정이 조금씩 살아나는 것 같습니다. 특히 제가 개발 공부를 시작하면서 느꼈던 재미를 다시 느끼고 있어서 너무 좋고 하루하루가 뿌듯한 것 같네요 ㅎㅎ 더 파이팅해야겠습니다! 👍🏻 이 글을 읽는 모든 분들께도 파이팅이 전달되면 좋겠네요💜 오늘도 같이 힘내봅시다 ~!

 

---

💬 문제

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

프로그래머스

 

---

💬 Idea

1. 불량 사용자 id에 해당하는 사용자 id의 인덱스를 저장할 수 있도록 dictionary를 만들고, 반복문을 돌면서 dictionary에 값을 채운다.
   • ["fr*d*": ["frodo", “fradi”], "*rodo": ["frodo", "crodo"], "*****": ["abc123", "frodoc"]] 를 떠올리며 추후에 dfs를 수행할 때 편리하도록 실제 구현시에는 사용자 id의 인덱스값을 저장한다.
   • ⇒ ["fr*d*": Set([0, 1]), "*rodo": Set([0, 2]), “*****”: Set([3, 4])]
2. dfs를 수행하며 불량 제재 아이디와 사용자 아이디를 맵핑한 쌍을 만든다.
   • dfs를 활용해야겠다고 떠올리면서, dfs의 깊이(=depth)를 banned_id 배열의 index로 응용하였다.
   • 즉, banned_id = ["fr*d*", "abc1**"] 의 경우
     • depth가 0일 때 → fr*d*에 해당하는 user_id가 결정되고
     • depth가 1일 때 → abc1** 에 해당하는 user_id가 결정된다.
     • 이렇게 depth가 깊어지면서 banned_id에 해당하는 유저의 id가 하나씩 결정되므로 depth의 최종 깊이가 되었을 때 하나의 제재 아이디 목록(bannedCase) 쌍이 생긴다.
   💡 [ dfs 설계 ] 
   • visited: user_id의 방문 여부(=현재 쌍에 포함되었는지)를 저장하는 visited 배열이다.
   • depth : 불량 아이디 목록의 index로서, dfs의 깊이를 뜻한다.
   • userIdx: 유저 아이디의 인덱스이다. visited 여부를 파악하고, 제재 아이디 쌍을 만드는데 사용된다.
   • bannedCase: 제재 아이디 쌍이 저장되는 Set<String>형 배열이다.
   1. 현재 userIdx가 방문되지 않았다면, 현재 userIdx를 방문처리하고, bannedCase에 현재 user_id를 저장한다.
   2. 이후 다음 깊이가 존재한다면 (depth + 1가 banned_id의 개수보다 작다면)
      • 다음 깊이에 해당하는 제재 id 후보들을 차례로 돌며 dfs를 수행한다.
   3. 제재 아이디 쌍의 개수가 깊이와 같아졌다면 제재 아이디 쌍을 저장하는 bannedCases에 해당 쌍을 저장하고 함수를 종료한다.
3. 제재 아이디 목록들을 구했을 때 아이디들이 나열된 순서와 관계없이 아이디 목록의 내용이 동일하다면 같은 것으로 처리하여 하나로 세면 됩니다 라는 조건을 해결하기 위해서 Set<Set<String>> 자료구조를 사용해주었다.
   • 해당 조건을 처리하기 위해 처음에는 bannedCases를 Set<[String]> 으로 디자인하여 하나의 제재 아이디 목록(bannedCase)이 만들어지면 해당 배열을 정렬하여 bannedCases에 insert해주었다.
   하지만 해당 작업이 시간초과를 유발한다는 것을 깨닫고 bannedCases 자체를 Set<Set<String>> 자료구조로 바꿔 구현해주었다.
   → 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(_ depth: Int, _ userIdx: Int, _ bannedCase: Set<String>, _ visited: [Bool]) {
        var bannedCase = bannedCase
        var visited = visited
        
        // 현재 userIdx가 방문되지 않았다면
        if !visited[userIdx] {
            // 현재 userIdx를 방문처리
            visited[userIdx] = true
            // bannedCase에 현재 user_id를 저장
            bannedCase.insert(user_id[userIdx])
            
            // 다음 깊이가 존재한다면
            if depth + 1 < banned_id.count {
                // 다음 깊이에 해당하는 제재 id 후보들을 차례로 돌며
                for i in banUserDict[banned_id[depth + 1]]! {
                    // dfs를 수행
                    dfs(depth + 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 = ["fr*d*", "abc1**"]
   perm[0]인 ["frodo", "fradi"] 를 예로 들어보자. (perm[0]을 p로 지칭하겠다.)
   p[0] = "frodo" 와 banned_id[0] = "fr*d*" 를 맵핑하여 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 방법이 훨씬 더 좋은 효율을 가지기 때문에 dfs가 더 좋은 풀이가 아닐까 생각이 들었다. 😊😊

 

 

 

https://github.com/hwangJi-dev/swiftAlgorithm/blob/main/Programmers/Programmers/level3/%EB%B6%88%EB%9F%89%20%EC%82%AC%EC%9A%A9%EC%9E%90.swift

GitHub - hwangJi-dev/swiftAlgorithm: Algorithm Practice with Swift