[프로그래머스] 후보키

 

 

▼ 문제 링크

코딩테스트 연습 - 후보키

 

다른 문제들 보다도 유난히 카카오에서 나온 문제들은 문제 길이가 엄청나게 길다. 상대적으로도, 절대적으로도... 그래서 문제 이해하는 데 에도시간이 소요되는 편인데, 이 문제를 풀기 위해 필요한 요건들을 정리하면 다음과 같다.

 

1. 주어진 데이터베이스의 속성으로 가능한 모든 조합을 만든다.
2. 이 조합들을 가지고 유일하게 튜플을 구분할 수 있는 조합을 찾는다. (보조키의 유일성)
3. 2에서 찾은 조합 중에서 최소성을 만족하지 않는 조합을 제외한다.

 

보조키의 유일성과 최소성에 대해서는 문제에 나와있다.

유일성(uniqueness) : 릴레이션에 있는 모든 튜플에 대해 유일하게 식별되어야 한다.
최소성(minimality) : 유일성을 가진 키를 구성하는 속성(Attribute) 중 하나라도 제외하는 경우 유일성이 깨지는 것을 의미한다.
즉, 릴레이션의 모든 튜플을 유일하게 식별하는 데 꼭 필요한 속성들로만 구성되어야 한다.

 

 

위 세 단계로 나누어 코드를 짜면 생각보다 쉽게 문제를 해결할 수 있다. (사실 쉽게 해결하진 못했다. 거의 반나절은 걸렸다. 방법을 늦게 깨달았을 뿐이지🥲 그치만 어쨋든 해결했고 어떻게 해야하는지 스스로 찾아냈으니까... 역시 삽질은 중요하다...)

 

 

1단계: 주어진 데이터베이스의 속성으로 가능한 모든 조합을 만든다.

// 주어진 keys가 가질 수 있는 모든 조합 만들기
private func getAllKeyCases(_ keys: [Int]) -> [[Int]] {
    var keyCases: [[Int]] = []
    
    // keys: 조합을 만들 때 고려할 수 있는, 앞서 사용하고 남은 요소들
    // index: 조합을 만들 때 추가할 요소를 가리키고 있는 인덱스
    // before: 이전까지 만든 조합 결과물
    func makeKeyCases(_ keys: [Int], _ index: Int, _ before: [Int]) {
        var k = keys
        var b = before
        
                // 중복으로 고려하는 걸 막기 위해 remove
        b.append(k.remove(at: index))
        keyCases.append(b)
            
                // 중복으로 고려하는 걸 막기 위해 0이 아니라 index부터 시작
        for i in index..<k.count {
            makeKeyCases(k, i, b)
        }
    }
    
    for i in 0..<keys.count {
        makeKeyCases(keys, i, [])
    }
    
    return keyCases
}

'주어진 요소들로 만들 수 있는 모든 조합 찾기' 일 때는 기본적으로 재귀 함수를 사용한다고 보면 된다. 여기서 이제 조합의 전체 개수가 요소의 전체 개수인지, 아니면 개수가 달라지는지, 같은 요소에 순서만 다른 조합을 허용하는지 안하는지 등 세부적인 요건이 달라질 뿐.

 

2단계: 이 조합들을 가지고 유일하게 튜플을 구분할 수 있는 조합을 찾는다.

// 주어진 keys들로 튜플을 구분할 수 있는 유일성을 만족하는지 체크
private func isUnique(_ keys: [Int], _ relation: [[String]]) -> Bool {
    var sets = Set<String>()

    for tuple in relation {
        var candidateKey = ""

        for key in keys {
            candidateKey += tuple[key]
        }
        
        if sets.contains(candidateKey) {
            return false
        } else {
            sets.insert(candidateKey)
        }
    }

    return true
}

(keys: 속성의 인덱스 값이 들어있는 배열)

candidateKey를 문자열로 지정했는데, 쉽게 풀면 다음과 같다.

예를 들어, 데이터가 위와 같고, 넘어온 keys값이 [1, 3]이라면 candidateKey는 튜플을 돌면서 각 튜플에 맞게 생성된다.
첫번째 튜플에서는 속성의 1번 값인 이름 ryan + 속성의 3번 값인 학년 2 = ryan2 가 된다.
두번째 튜플에서는 같은 방법으로 apeach2
이런식으로 반복하는데 여섯번째 튜플에서 apeach2라는 값이 중복으로 생기기 때문에 이 조합은 보조키의 유일성을 충족하지 못한다.

이 함수를 통해 해당 속성의 조합이 유일성을 보장하는지 아닌지 확인할 수 있다.

 

3단계: 2에서 찾은 조합 중에서 최소성을 만족하지 않는 조합을 제외한다.

제일 고생했던 구간이다. ㅠ ㅠ

// 유일성을 만족하는 보조키 중 최소성 체크하기
for (idx, ck) in candidateKeys.enumerated() {
    // 보조키 조합이 가지는 모든 종류의 조합
    let allCase = getAllKeyCases(ck)
    var tempCandidateKeys = candidateKeys
    // 자기 자신을 중복 체크하는 경우가 발생하지 않도록
    tempCandidateKeys.remove(at: idx)

    for ac in allCase {
        if tempCandidateKeys.contains(ac) {
            candidateKeys[idx] = []
        }
    }
}

유일성을 만족하는 속성의 조합이 최소성을 만족하는지 체크하려면, 다시 한 번 해당 조합으로 만들 수 있는 모든 조합을 생성해야 한다.
그리고 그 모든 조합이 다른 보조키 후보 조합을 가지고 있다면 해당 보조키 조합은 최소성을 만족하지 않는다.

(candidateKeys의 index를 유지하기 위해 remove하지 않고 보조키 조합을 빈 배열[]로 대치했다.)

 

전체 코드

import Foundation

func solution(_ relation: [[String]]) -> Int {
    // tuple의 인덱스를 key종류로 만들기 위해 배열을 만들어 인덱스만 추가하기
    var keys: [Int] = []
    
    for i in 0..<relation.first!.count {
        keys.append(i)
    }
    
    // candidateKey가 될 수 있는 모든 index의 조합
    let allKeys: [[Int]] = getAllKeyCases(keys)
    var candidateKeys: [[Int]] = []
    
    // 모든 index조합 중 유일성을 만족하는 index의 조합
    for ak in allKeys {
        if isUnique(ak, relation) {
            candidateKeys.append(ak)
        }
    }
    
    // 유일성을 만족하는 보조키 중 최소성 체크하기
    for (idx, ck) in candidateKeys.enumerated() {
        // 보조키 조합이 가지는 모든 종류의 조합
        let allCase = getAllKeyCases(ck)
        var tempCandidateKeys = candidateKeys
        // 자기 자신을 중복 체크하는 경우가 발생하지 않도록
        tempCandidateKeys.remove(at: idx)
        
        for ac in allCase {
            if tempCandidateKeys.contains(ac) {
                candidateKeys[idx] = []
            }
        }
    }

    return candidateKeys.filter({ !$0.isEmpty }).count
}

// 주어진 keys들로 튜플을 구분할 수 있는 유일성을 만족하는지 체크
private func isUnique(_ keys: [Int], _ relation: [[String]]) -> Bool {
    var sets = Set<String>()

    for tuple in relation {
        var candidateKey = ""

        for key in keys {
            candidateKey += tuple[key]
        }
        
        if sets.contains(candidateKey) {
            return false
        } else {
            sets.insert(candidateKey)
        }
    }

    return true
}

// 주어진 keys가 가질 수 있는 모든 조합 만들기
// <재귀 함수 이용>
private func getAllKeyCases(_ keys: [Int]) -> [[Int]] {
    var keyCases: [[Int]] = []
    
    // keys: 조합을 만들 때 고려할 수 있는, 앞서 사용하고 남은 요소들
    // index: 조합을 만들 때 추가할 요소를 가리키고 있는 인덱스
    // before: 이전까지 만든 조합 결과물
    func makeKeyCases(_ keys: [Int], _ index: Int, _ before: [Int]) {
        var k = keys
        var b = before
        
                // 중복으로 고려하는 걸 막기 위해 remove
        b.append(k.remove(at: index))
        keyCases.append(b)
            
                // 중복으로 고려하는 걸 막기 위해 0이 아니라 index부터 시작
        for i in index..<k.count {
            makeKeyCases(k, i, b)
        }
    }
    
    for i in 0..<keys.count {
        makeKeyCases(keys, i, [])
    }
    
    return keyCases
}