[Swift] 프로그래머스 - 후보키

문제: https://programmers.co.kr/learn/courses/30/lessons/42890

코딩테스트 연습 - 후보키

 

 

1. 후보키가 될 수 있는 인덱스들을 전부 조합으로 뽑아줍니다.

2. 그 인덱스들이 갖고 있는 값이 중복되지 않는지(유일성) 검사해줍니다.

3. 최소성을 검사합니다.

4. 후보키들을 result 배열에 넣고 카운트를 리턴합니다.

import Foundation

func combi(_ nums: [Int], _ targetNum: Int) -> [[Int]] {
    var result = [[Int]]()
    
    func combination(_ index: Int, _ nowCombi: [Int]) {
        if nowCombi.count == targetNum {
            result.append(nowCombi)
            return
        }
        for i in index..<nums.count {
            combination(i + 1, nowCombi + [nums[i]])
        }
    }
    
    combination(0, [])
    
    return result
}

func solution(_ relation:[[String]]) -> Int {
    var result = [[Int]]()
    var possibles = [[Int]]() // indices
    
    let keys = relation[0].count
    let allKeys = Array(0..<keys)
    for i in 1...keys {
        combi(allKeys, i).forEach { possibles.append($0) }
    }
    
    for possible in possibles {
        let relation1 = relation.map { $0.enumerated().filter { (index, value) in possible.contains(index) }.map { $1 } }
        let s1 = Set(relation1)
        
        if relation1.count == s1.count { // 유일성 검사
            var isContain = false
            
            result.forEach {
                if Set($0).isSubset(of: possible) { // 최소성 검사
                    isContain = true
                }
            }
            
            if !isContain {
                result.append(possible)
            }
        }
    }
    
    return result.count
}

solution([["100","ryan","music","2"],["200","apeach","math","2"],["300","tube","computer","3"],["400","con","computer","4"],["500","muzi","music","3"],["600","apeach","music","2"]]) // 2