후보키.md

후보키

실패

func isRemainKeys(remainKeys: [Int], selected: [Int]) -> Bool {
    for num in selected {
        if !remainKeys.contains(num) {
            return false
        }
    }
    
    return true
}

func solution(_ relation:[[String]]) -> Int {
    var result = 0
    var remainKeys = (0..<relation[0].count).map({ $0 })
    
    var visited = Array(repeating: false, count: relation.count)
    
    func back(index: Int, target: Int, selected: [Int]) {
        if selected.count == target && isRemainKeys(remainKeys: remainKeys, selected: selected) {
            var test = Set<String>()
            for r in 0..<relation.count {
                let word = selected.reduce(into: "") { result, col in
                    result += relation[r][col]
                }
                test.update(with: word)
            }
            
            if test.count == relation.count {
                for num in selected {
                    remainKeys.removeAll(where: { $0 == num })
                }
                result += 1
            }
        }
        
        for i in index..<relation[0].count {
            if visited[i] {
                continue
            }
            visited[i] = true
            back(index: i, target: target, selected: selected + [i])
            visited[i] = false
        }
    }
    
    for i in 1...relation[0].count {
        visited = Array(repeating: false, count: relation.count)
        back(index: 0, target: i, selected: [Int]())
    }
    
    return result
}

https://velog.io/@sainkr/프로그래머스-후보키-Swift

import Foundation

//reference: https://velog.io/@sainkr/프로그래머스-후보키-Swift
func isRemainKeys(remainKeys: [Int], selected: [Int]) -> Bool {
    for num in selected {
        if !remainKeys.contains(num) {
            return false
        }
    }
    
    return true
}

func solution(_ relation:[[String]]) -> Int {
    var visited = Array(repeating: false, count: relation[0].count)
    
    var selectedNums = [[Int]]()
    
    func back(index: Int, target: Int, selected: [Int]) {
        if selected.count == target {
            selectedNums.append(selected)
        }
        
        for i in index..<relation[0].count {
            if visited[i] {
                continue
            }
            visited[i] = true
            back(index: i, target: target, selected: selected + [i])
            visited[i] = false
        }
    }
    
    for i in 1...relation[0].count {
        visited = Array(repeating: false, count: relation[0].count)
        back(index: 0, target: i, selected: [Int]())
    }
    
    var i = 0
    while i < selectedNums.count {
        var test = Set<String>()
        for r in 0..<relation.count {
            let word = selectedNums[i].reduce(into: "") { result, col in
                result += relation[r][col]
            }
            test.update(with: word)
        }
        
        if test.count == relation.count {
            var c = 0
            
            while c < selectedNums.count{
                var cnt = 0
                for l in selectedNums[i].indices{
                    if selectedNums[c].contains(selectedNums[i][l]){
                        cnt += 1
                    }
                }
                
                if selectedNums[i] != selectedNums[c] && cnt == selectedNums[i].count{
                    selectedNums.remove(at: c)
                }else{
                    c += 1
                }
            }
            i += 1
        } else {
            selectedNums.remove(at: i)
        }
        
    }
    
    return selectedNums.count
}

좋은 풀이

func solution(_ relation:[[String]]) -> Int {
    let rowSize = relation.count
    let colSize = relation[0].count

    var resultSet = Set<Int>()

    for bit in 1..<(1<<colSize) {
        var combiSet = Set<String>()
        var isUnique = true

        for r in 0..<rowSize {
            var tmpStr = "" 
            for c in 0..<colSize where (bit & (1<<c)) != 0 { 
                tmpStr += relation[r][c] 
            } 
            if combiSet.update(with: tmpStr) != nil { // set내에 중복 요소 존재
                isUnique = false
                break
            }
        } 

        if isUnique && resultSet.filter{ ($0 & bit) == $0 }.isEmpty {
            resultSet.insert(bit)
        } 
    }

    return resultSet.count 
}

다른 풀이

https://fomaios.tistory.com/entry/2019-KAKAO-BLIND-RECRUITMENT-%ED%9B%84%EB%B3%B4%ED%82%A4-Swift