코딩테스트 연습 - 불량 사용자

문제 풀이 아이디어

문제의 조건과 예시를 보면 불량 사용자를 의미하는 “*”이 들어간 불량 id는 여러 개의 id와 매칭이 될 수 있습니다. 반대로 하나의 id가 여러 개의 불량 id와 매칭이 될 수 있습니다. id와 불량 id는 1 : 1의 관계도 1 : N의 관계도 아닌 N : M의 관계를 가지게 됩니다.

이런 경우 정말 “모든” 케이스를 비교할 수 밖에 없습니다. 어떤 id를 먼저 체크하느냐의 (= id를 불량 id와 매칭하는 순서) 조차도 결과에 영향을 줄 수 있기 때문에 id의 순서도 모두 바꿔가면서 매칭을 해보아야 합니다.

이럴 때는 순열을 사용해서 id 중에 불량 id의 갯수만큼 뽑아 리스트를 만든 다음에 해당 id 리스트가 불량 id 리스트와 일치하는지 찾아야 합니다. id에서 순열을 구하므로 굳이 불량 id 리스트의 순서를 섞을 필요는 없습니다.

Swift로 순열 구하기

Swift는 순열을 직접 구현해야 합니다. 이 포스팅을 참고해주세요.

zip 활용하기

두 Sequence를 짝지어 사용하는 함수입니다. zip을 사용해서 두 배열을 묶게 되면 굳이 index를 사용하지 않아도 동일한 index에 있는 원소를 활용할 수 있습니다.

만약에 두 Sequence의 길이가 다르다면 짧은 쪽을 기준으로 짝지어 집니다.

코드

// id와 *처리 된 단어가 일치하는지 확인하는 함수
func isMatch(_ id: String, _ banned: String) -> Bool {
    // 길이가 다르면 false
    guard id.count == banned.count else { return false }
    
    // 한 글자씩 비교
    for (char1, char2) in zip(id, banned) {
        // "*"일 경우에는 비교하지 않음
        if char2 == "*" { continue }
        // "*"이 아닌 부분이 다를 경우 false
        if char1 != char2 { return false }
    }
    
    // 반복문을 통과하면 (= "*"를 제외한 부분이 동일하면) true 리턴
    return true
}

// 순열 구하는 함수
func permutation(_ array: [String], _ length: Int) -> [[String]] {
    var result = [[String]]()
    var visited = Array(repeating: false, count: array.count)
    
    func permute(_ now: [String]) {
        if now.count == length {
            result.append(now)
            return
        }
        
        for i in 0..<array.count {
            if !visited[i] {
                visited[i] = true
                permute(now + [array[i]])
                visited[i] = false
            }
        }
    }
    
    permute([])
    return result
}

func solution(_ user_id:[String], _ banned_id:[String]) -> Int {
    // "아이디의 목록"은 순서에 관계 없음 -> Set<String> = id끼리 중복되면 안됨
    // ids(순열)과 banned_id를 비교하는 과정에서 중복된 "아이디의 목록"이 나올 수 있음 -> Set<Set<String>> = "id의 목록"끼리 중복되면 안됨
    var ans = Set<Set<String>>()
    
    // user_id를 순열로 만들어서 id의 목록 만들기
    for ids in permutation(user_id, banned_id.count) {
        var count = 0 // ids[i]가 banned_id[i]와 일치하는 갯수
        for (id, banned) in zip(ids, banned_id) {
            if isMatch(id, banned) {
                count += 1
            }
        }
        // banned_id와 일치하면 ids를 Set으로 바꾸어서 ans에 추가
        if count == banned_id.count {
            ans.insert(Set(ids))
        }
    }
    
    return ans.count
}