[프로그래머스] (Swift) Kakao - 후보키 (Lv.2)

🟠 문제 링크

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

프로그래머스

 

🟠 나의 풀이

후보키가 될 수 있는 조합을 생각해야했다. 그래서 combination 함수를 사용했다. 

//n개중 m를 순서에 상관없이 뽑아야할 조합들을 만들어주는 함수
func combination(n: [Int], m: Int, current index: Int, pickedArray: [Int]) {
    if m == 0 {
        cases.append(pickedArray)
    }else if index == n.count {
        return
    }else {
        var newSelected = pickedArray
        newSelected.append(n[index])
        combination(n: n, m: m-1, current: index+1, pickedArray: newSelected)
        combination(n: n, m: m, current: index+1, pickedArray: pickedArray)
    }
}

이 함수를 사용하면 아래와 같은 결과를 얻을 수 있다.

// 사용법
var temp = [1, 2, 3, 4, 5]
for i in 0..<temp.count {
    combination(n: temp, m: i+1, current: 0, pickedArray: [])
}
print(cases)

이렇게 모든 후보키들의 조합을 얻을 수 있다.

 

이렇게 구하게 되면, 해당 후보키에 해당하는 value들을 넣고, value들의 모음의 길이가 relation 길이와 같다면 조건에서 주어진 '유일성'을 만족하는 것이다. (아래 사진)

이제 조건에서 주어진, 최소성을 만족하는가를 봐야하는데, 이부분이 살짝 이해가 가질 않았다. 위 사진 예시로 보면 [학번, 이름] 이 이미 후보키의 부분집합에 해당한다면, 최소성을 만족하지 못하는 것으로 간주한다.  (아래 설명)

🟠 정답 코드

https://github.com/deslog/Algorithm/blob/main/Algorithm/Programmers/kakao_%ED%9B%84%EB%B3%B4%ED%82%A4/main.swift

GitHub - deslog/Algorithm

import Foundation

//조합들을 담을 배열
var cases = [[Int]]()

func solution(_ relation:[[String]]) -> Int {
    var candidateKey = [[Int]]()
    var colsize = [Int]()

    for i in 0..<relation[0].count {
        colsize.append(i)
    }
    // 컬럼수들의 조합 생성
    for i in 0..<colsize.count {
        combination(n: colsize, m: i+1, current: 0, pickedArray: [])
    }

    // 최소성 확인 isSuperset() 부분집합인지 확인
    out: for c in cases {
    //최소성을 만족하는지 확인
        let set = Set(c)
        //후보키들을 탐색
        for key in candidateKey {
            //후보키 안에 현재 key가 포함된게 있다면 넘어간다.
            if set.isSuperset(of: key) {
                continue out
            }
        }

        var rowSet = Set<Array<String>>()
        // row별로 combi에 있는 속성들만 뽑아서 확인
        for row in relation {
            var tuple = [String]()

            for i in c {
                tuple.append(row[i])
            }

            if !rowSet.contains(tuple) {
                rowSet.insert(tuple)
            } else {
                break
            }
        }

        if rowSet.count == relation.count {
            candidateKey.append(c)
        }
    }

    return candidateKey.count
}

//n개중 m를 순서에 상관없이 뽑아야할 조합들을 만들어주는 함수
func combination(n: [Int], m: Int, current index: Int, pickedArray: [Int]) {
    if m == 0 {
        cases.append(pickedArray)
    }else if index == n.count {
        return
    }else {
        var newSelected = pickedArray
        newSelected.append(n[index])
        combination(n: n, m: m-1, current: index+1, pickedArray: newSelected)
        combination(n: n, m: m, current: index+1, pickedArray: pickedArray)
    }
}