[프로그래머스] Swift - 불량 사용자

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

프로그래머스

 

2023.07.11 기준 Level 3

 

알고리즘 공부용으로 풀고 기록하는 글입니다!
참고만 해주시고 더 좋은 풀이법이 있다면 알려주세요!

 

아이디어

불량 사용자에 매칭되는 userId 들의 경우의 수를 구하는 문제입니다.

순차적으로 해결해 보고자 했습니다.

user_id 배열의 크기가 8 이하이기 때문에 작은 값입니다. 따라서 여러번 반복문을 통해 순회해도 시간초과에 걸릴 가능성이 낮다는 것도 인지하면서 시작했습니다.

 

1. 세부적인 문제 해결에 앞서 우선 각 bannedId에 매칭될 수 있는 userId를 찾는 함수를 구현해야 합니다.

user_id 배열을 전부 돌며 매칭되는 케이스를 찾으면 됩니다.

banId(bannedId)와 userId의 길이가 같지 않다면 즉시 넘어가고, 알파벳이 한 곳이라도 다르면서 banId의 해당 위치가 "*"이 아니면 역시나 결과에 추가하지 않고 넘어갑니다.

 

2. 이렇게 나온 매칭 id 어레이들을 딕셔너리에 저장합니다.

key는 banId의 인덱스

value는 매칭되는 id 어레이입니다.

 

예시
user_id = ["frodo", "fradi", "crodo", "abc123", "frodoc"]
banned_id = ["fr*d*", "*rodo", "******", "******"]
주어진 값이 위와 같을 때 2번까지의 과정을 거치면 다음과 같은 딕셔너리를 얻을 수 있습니다.

[1: ["frodo", "crodo"], 3: ["abc123", "frodoc"], 0: ["frodo", "fradi"], 2: ["abc123", "frodoc"]]

 

3. 현재는 각 banId에 해당하는 userId 어레이들이 딕셔너리 형태에 저장되어 있기 때문에 이제 이 userId 어레이에서 1개씩 빼와서 경우의 수를 만들어 나가면 됩니다.

반복문을 통해 하나씩 골라서 넣거나 재귀(dfs)를 통해 경우의 수를 구할 수 있습니다.

저는 dfs를 사용했습니다.

여기서 중요한 점은 구한 경우의 수에서 각 id값의 순서가 다르더라도 같은 경우의 수로 인식해야 하기 때문에 Set을 사용하여 저장하도록 했습니다.

Set을 사용하게 되면 insert 시에 자동으로 중복이 제거되기 때문에 효율적입니다.

dfs에서 경우의 수를 구할 때도 Set에 userId를 넣으면서 구하고

dfs에서 결과물로 구한 경우의 수들을 저장할 때도 Set을 사용하여 Set에 Set을 넣는 구조를 활용했습니다.

 

앞선 예시 상황에서 dfs를 돌고 나온 결과물들을 저장한 Set은 다음과 같이 출력됩니다. 이 Set의 count 값이 문제의 정답입니다.

[Set(["frodo", "crodo", "abc123", "frodoc"]), Set(["frodo", "abc123", "fradi", "frodoc"]), Set(["crodo", "frodoc", "fradi", "abc123"])]

 

풀이

fileprivate func solution(_ user_id:[String], _ banned_id:[String]) -> Int {
    var result = Set<Set<String>>()   // 가능한 경우의 수들이 들어갈 집합 (각 경우의 수도 집합으로 관리)
    
    var matchDict = [Int: [String]]() // key: banId의 index, value: 매칭되는 userIds 어레이
    
    for (i, banId) in banned_id.enumerated() {
        matchDict[i] = findMatchingIds(userIds: user_id, banId: banId)
    }
        
    func dfs(level: Int, ids: Set<String>) {
        if level != ids.count { return }
        
        if level == banned_id.count {
            result.insert(ids)
            return
        }
        
        for matchId in matchDict[level]! {
            dfs(level: level+1, ids: ids.union([matchId]))
        }
    }
    
    dfs(level: 0, ids: [])
        
    return result.count
}

/// banId에 해당할 수 있는 userId 어레이 반환
fileprivate func findMatchingIds(userIds: [String], banId: String) -> [String] {
    var ids = [String]()
    
    outer: for userId in userIds {
        if userId.count != banId.count { continue }
        
        for idx in banId.indices {
            if userId[idx] != banId[idx] && banId[idx] != "*" {
                continue outer
            }
        }
        
        ids.append(userId)
    }
    
    return ids
}

 

 

마무리

3단계 문제치고는 난이도 자체가 높지는 않았지만 순차적으로 해결방법을 하나씩 찾아서 적용하는 과정이 필요했습니다.

user_id 배열의 크기가 작았기 때문에 완전 탐색을 하는 방식을 떠올렸고 중복을 제거해야 하기 때문에 Set을 적극적으로 사용하는 방식으로 아이디어의 흐름이 진행되었던 것 같습니다.

경우의 수들을 구하는 부분에서 dfs를 사용하는 것과 해당 dfs에서 base case를 잘 설정하는 것도 주요했습니다.