1. 문제 설명

후보키

2. 문제 분석

DFS를 통한 후보 키 조합, 후보 키의 미니멀/유니크함을 판별하는 각 로직 두 개를 통해 풀 수 있는 문제다.

• 가능한 후보 키 조합을 DFS를 통해 모았고, 조합에 들어간 칼럼의 인덱스 카운트를 오름차순으로 정렬해 처음부터 미니멀한 후보 키를 탐색하고자 했다.
• 후보키 조건을 판별하기 전 지금까지 등록한 후보키 자체를 포함하는 키 조합은 애초에 미니멀한 조건을 만족하지 않는다는 점을 통해 필터링했다.
• 이후에는 주어진 릴레이션 튜플마다 주어진 후보 키를 통해 새로운 튜플을 생성해 튜플 집합을 만들었다.
• 마지막으로 기존 튜플 개수와 비교해서 튜플 찾기의 유니크함이 보장되는지 확인했다. 유니크하다면 후보 키에 등록했다.

3. 나의 풀이

import Foundation

func solution(_ relation:[[String]]) -> Int {
    let columnCount = relation[0].count
    var candidates = [[Int]]()
    
    func depthFirstSearch(_ startIndex: Int, _ curIndices: [Int]) {
        if !curIndices.isEmpty {
            candidates.append(curIndices)
        }
        
        for idx in startIndex..<columnCount {
            depthFirstSearch(idx + 1, curIndices + [idx])
        }
    }
    depthFirstSearch(0, [])
    candidates.sort(by: {$0.count < $1.count})
    
    var candidateKeys = [[Int]]()
    let relationCount = relation.count
    for candidate in candidates {
        if !isCandidateMinimal(candidateKeys, candidate) {
            continue
        }
        
        var relationSet = Set<String>()
        for tuple in relation {
            let convertedTuple = convertTuple(tuple, candidate)
            relationSet.insert(convertedTuple)
        }
        if relationSet.count == relationCount {
            candidateKeys.append(candidate)
        }
    }
    
    return candidateKeys.count
}

func isCandidateMinimal(_ candidateKeys: [[Int]], _ candidate: [Int]) -> Bool {
    for candidateKey in candidateKeys {
        if Set(candidate).isSuperset(of: Set(candidateKey)) {
            return false
        }
    }
    return true
}

func convertTuple(_ tuple: [String], _ indices: [Int]) -> String {
    var tmp = ""
    let indices = indices.sorted(by: <)
    for index in indices {
        tmp += tuple[index]
    }
    return tmp
}