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

프로그래머스 - 후보키

나의 풀이

핵심은 1번째 컬럼이 후보키이면 1번째를 포함한 모든 컬럼은 후보키가 아니라는걸 알고 계시면 됩니다. 마찬가지로 (1번째, 2번째)가 후보키이면 (1, 2)를 포함한 모든 컬럼은 후보키가 아닙니다.

풀이 방법

1. 조합으로 컬럼이 짝 지을 수 있는 경우의 수를 구해줍니다. 문제에선 컬럼이 4개니까 [0], [1], [2], [3], [0,1], [0,2] ... [0,1,2,3] 이런식으로 모든 경우의 수를 구해주시면 됩니다.

2. 구한 경우의 수를 원소의 개수가 작은 것부터 정렬해줍니다. 원소의 개수가 작은것 부터 후보키인지 판별해주는 것 입니다. 예를 들면 [0]이 후보 키라 가정했을 때 [0] 부터 시작하면 0을 가지고 있는걸 다 지우면 되지만 [0, 1]부터 시작하면 [0, 1]을 포함한걸 다 지운 후 [0]일 때 다시 [0,1]을 지워야 되니 비효율적이겠죠 ??

이제 경우의 수를 다 구하고 정렬도 해서 numArr = [0], [1], [2], [3], [0,1], [0,2] ... [0,1,2,3] 이 됩니다.

3. 맨 처음인 [0]부터 후보키가 되는지 체크해줍니다.

4. [0]번째 컬럼이 만약 후보키가 된다면
   최소성을 지키기 위해 numArr에서 [0]을 포함하는 배열을 지워주면 됩니다. 예를 들면 [0,1], [0,2] ... [0,1,2,3]을 지워줍니다.

5. [0]번째 컬럼이 만약 후보키가 되지 않는다면 numArr에서 [0]을 지워줍니다.

6. 이제 3,4,5를 계속 반복해서 후보키의 수를 구하시면 됩니다.

import Foundation

var numArr: [[Int]] = [] // 조합으로 구한 경우의 수
func solution(_ relation:[[String]]) -> Int {
    // 1. 컬럼이 짝 지을 수 있는 경우의 수 다 구해주기
    for i in 0..<relation[0].count{
        combination(i, relation[0].count, [])
    }
    
    // 2
    numArr.sort{ $0.count < $1.count}
    
    var i = 0
    while i < numArr.count{
        var arr: [String] = []
        // 3. 컬럼이 유일한지 판별해줍니다.
        for m in relation.indices{
            var k = ""
            for n in numArr[i].indices{
                k += relation[m][numArr[i][n]]
            }
            if arr.contains(k){ // contain을 사용하여 유일한지 체크
                break // 포함하고 있다면 break
            }else{ // 포함하지 않는다면 append
                arr.append(k)
            }
        }
        
        // 4
        if arr.count == relation.count{ // arr과 튜플의 수가 같을 때 즉 다 유일할 때
            var c = 0
            
            while c < numArr.count{
                var cnt = 0
                for l in numArr[i].indices{ // 해당 컬럼을 가지고 있는지 체크 
                    if numArr[c].contains(numArr[i][l]){
                        cnt += 1
                    }
                }
               
                if numArr[i] != numArr[c] && cnt == numArr[i].count{ // 만약 다 가지고 있다면 
                    numArr.remove(at: c) // 제거
                }else{
                    c += 1
                }
            }
            i += 1
        }else{ // 유일하지 않다면 제거
            numArr.remove(at: i) 
        }
    }
    
    return numArr.count
}
// 조합
func combination(_ s: Int, _ cnt: Int, _ arr: [Int]){
    if s == cnt {
        numArr.append(arr)
        return
    }else {
        var arr = arr
        for i in s..<cnt{
            arr.append(s)
            combination(i + 1, cnt, arr)
            arr.removeLast()
        }
    }
}