[Swift 알고리즘] 프로그래머스(Lv.2) - 후보키 / 2019 카카오 블라인드

안녕하세요. 개발 중인 정주입니다.

 

오늘은 "프로그래머스(Lv.2) - 후보키" 문제를 풀었습니다.

 

---

Github

GitHub - jeongju9216/SwiftAlgorithm: 스위프트 알고리즘

 

문제 링크

코딩테스트 연습 - 후보키

 

---

풀이

이번 문제는 집합을 응용해야 하는 문제입니다.

중복 부분 조합..이라고 해야 할까요?

부분 조합인데 중복을 허용해야 합니다.

 

1. 주어진 키로 만들 수 있는 조합의 모든 경우의 수를 구해야 합니다.

1개를 선택하는 경우부터 모두 선택하는 경우까지 모든 경우의 수를 구해야 합니다.

이 문제에서 까다로운 것은 중복을 허용해야 하기 때문에 Set을 사용할 수 없다는 점입니다.

전 재귀를 이용해 하나하나 구해주었습니다. (combi( ) 참고)

 

2. 키가 최소성을 만족하는지 확인합니다.

후보키는 최소성을 만족해야 합니다.

체크 중인 키가 후보키를 포함하고 있다면 그 키는 최소성을 만족하지 않습니다.

Swift에서 지원하는 isSuperset( )을 이용해 부분 집합인지 확인했습니다.

 

3. 유일성을 만족하는지 확인합니다.

유일성은 Dictionary를 이용했습니다.

만약 Dictionary에 키가 이미 존재한다면 중복이 된다는 의미이므로 유일성을 만족하지 못합니다.

 

4. 후보키에 넣습니다.

딕셔너리 키의 개수가 입력된 tuple의 개수와 동일하다면 후보키로 넣습니다.

마지막에 후보키의 개수를 return 합니다.

 

후기

중복이 허용되는 집합 문제는 상당히 까다롭다는 것을 느꼈습니다.

중복 부분 집합을 구하는 것도 일이었고 최소성을 구하는 것도 isSuperset( )이 없었다면 시간이 걸렸을 거 같습니다.

isSuperset( )은 유용하게 쓰일 것 같으니 기억해야겠습니다.

Apple Developer Documentation

 

---

전체 코드

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 {
    let colCount = relation.first!.count
    let tupleCount = relation.count
    print("colCount: \(colCount)")
    
    var keyCases: [Int] = (0..<colCount).map { $0 }
    print("keyCases: \(keyCases)")
    
    var combinations: [[[Int]]] = []
    for i in 1...colCount {
        let combos: [[Int]] = combi(keyCases, i)
        combinations.append(combos)
        // print("combos: \(combos)")    
    }
    print("combinations: \(combinations)")
    
    var candidateKeys: [[Int]] = []
    for combination in combinations {
        for combination2 in combination {
            //최소성 판단
            let set = Set(combination2)
            var isMinimal = true
            for key in candidateKeys {
                if set.isSuperset(of: key) {
                    isMinimal = false
                    break
                }
            }
            
            guard isMinimal else { continue }
            
            //유일성 판단
            var dict: [String: Bool] = [:]
            for tp in relation {
                var key: String = ""
                for combi in combination2 {
                    key += tp[combi]
                }

                if let _ = dict[key] { //후보키가 아님
                    break
                } else {
                    dict[key] = true    
                }
            }
            
            if dict.count == tupleCount {
                candidateKeys.append(combination2)
            }
        }
    }
    
    print("candidateKeys: \(candidateKeys)")
    return candidateKeys.count
}

---

아직은 초보 개발자입니다.

더 효율적인 코드 훈수 환영합니다!

공감과 댓글 부탁드립니다.