[Algorithm] 후보키

[hwangJi-dev]

💬 문제

[코딩테스트 연습 - 후보키](https://school.programmers.co.kr/learn/courses/30/lessons/42890)

💬 Idea

1. 릴레이션의 컬럼 개수만큼 돌며 컬럼의 조합을 구한다.
2. 조합이 추출되었을 때마다 이미 추출된 후보키 조합에 현재 조합이 속하는지 검사해준다.
   1. ex) now: [1, 2, 3] e: [1, 3]
      => 이미 추출된 후보키 조합에 현재 조합이 속하여 “최소성”에 부합하지 않으므로 제외되어야 한다
3. 속하지 않는다면 최소성을 만족한다는 것이다. 이제 validateKey 메서드를 호출하여 현재 조합이 후보키 조건인 “유일성”을 만족하는지 검사해준다.
4. validateKey 메서드 실행 결과가 true라면 유일성 조건까지 만족하는 것이므로 result에 1을 더해준다.

💬 풀이

var exception: [[Int]] = []

func solution(relation:[[String]]) -> Int {
    var ans = 0
    
    for i in 1...relation[0].count {
        ans += combination([Int](1...relation[0].count), i, relation)
    }
    
    return ans
}

// MARK: 조합을 추출하고 해당 조합이 후보키를 만족하는지 판별하여 후보키의 개수를 리턴하는 메서드
func combination(_ array: [Int], _ n: Int, _ relation: [[String]]) -> Int {
    var result = 0
    if array.count < n { return result }
    
    func cycle(_ index: Int, _ now: [Int]) {
        if now.count == n {
            // 이미 추출된 후보키 조합에 현재 조합이 속하는지 검사
            for e in exception {
                var arr: [Bool] = []
                for i in e {
                    if now.contains(i) {
                        arr.append(true)
                    }
                }
                
                // 속한다면 
                if arr.count == e.count {
                    // 후보키를 만족하는지 판별하지 않고 넘어간다
                    return
                }
            }
            
            // 속하지 않는다면 후보키를 만족하는지 판별한다
            if validateKey(comb: now, relation: relation) {
                // 후보키를 만족하는 조합이라면 결과에 +1
                result += 1
                // 예외가 되어야하므로 exception 배열에 append
                exception.append(now)
            }
            
            return
        }
        
        for i in index..<array.count {
            cycle(i + 1, now + [array[i]])
        }
    }
    
    cycle(0,[])
    
    return result
}

// MARK: 현재 조합이 후보키를 만족하는지 판별하는 메서드
func validateKey(comb: [Int], relation: [[String]]) -> Bool {
    var isKey = true
    var dict: [[String]: String] = [:]
    
    for r in 0..<relation.count {
        var key: [String] = []
        for c in comb {
            key.append(String(relation[r][c - 1]))
        }
        
        if dict[key] == nil {
            dict[key] = ""
        } else {
            dict.removeAll()
            isKey = false
            break
        }
    }
    
    return isKey ? true : false
}