문제 풀이 아이디어

문제의 정의

유일성

해당 속성들로 key를 만들었을 때 모든 row들이 각각 유일하게 식별되어야 합니다.

이를 코드로 옮기면 해당 속성으로 key를 만들어서 set에 넣고 (중복 제거를 위해서) 해당 set의 길이와 row의 갯수가 동일하면 유일성을 가진다고 볼 수 있습니다.

최소성

유일성을 가진 키를 구성하는 속성 중에 하나라도 빠지면 유일성이 깨져야 합니다. 예를 들면 [속성1, 속성2, 속성3]이 유일성을 가지는 키라고 할 때 [속성1, 속성2], [속성2, 속성3], [속성1, 속성3]으로 구성된 키는 무조건 유일성을 가지지 않아야 합니다.

다르게 말하면 [속성1, 속성2, 속성3]에 다른 속성을 포함한 키는 모두 최소성을 위반한다는 것입니다. [속성1, 속성2, 속성3, 속성4]의 경우 유일성을 가진다고 하더라도 속성4가 빠졌을 때도 유일성이 깨지지 않으므로 최소성을 위반합니다.

이를 코드로 옮기면 유일성과 최소성을 만족하는 A키가 B키의 부분집합일 경우 B키는 최소성의 원칙을 위반한 키입니다.

문제 풀이 과정

먼저 후보키가 될 수 있는 조합을 구해야 합니다. 키를 구성하는데 있어서 속성의 순서는 관계없으므로 조합을 통해서 (여기서는 column의 순서대로) 후보키의 후보가 되는 키들을 만듭니다. (길이 1 ~ column의 갯수)

그리고 해당 key들을 유일성과 최소성 검사를 해서 후보키가 될 수 있는지 구하면 됩니다.

유일성 검사는 크게 어려움이 없습니다만, 최소성의 경우 주의할 점이 있습니다. “부분집합”이라는 개념을 활용하기 때문에 key들을 후보키가 될 수 있는지 판별할 때 “길이가 짧은 순서대로” 판별해야 한다는 점입니다.

이하 과정은 코드의 주석으로 참고해주세요.

코드

// 조합을 구하는 함수
func combination(_ array: [Int], _ length: Int) -> [[Int]] {

    var result = [[Int]]()

    func combi(_ now: [Int], _ index: Int) {
        if now.count == length {
            result.append(now)
            return
        }

        for i in index..<array.count {
            combi(now + [array[i]], i + 1)
        }

    }

    combi([], 0)

    return result

}

// 최소성을 확인하는 함수
    // 기존의 이미 구한 키의 속성을 모두 포함하고 있으면 안된다.
    // = 기존의 구한 키는 이미 꼭 필요한 속성만으로 구성되어 있으므로
func isMinimal(_ now: [Int], _ keys: [[Int]]) -> Bool {
    for key in keys {
        if Set(key).isSubset(of: Set(now)) { return false }
    }
    return true
}

// 유일성을 확인하는 함수
func isUnique(_ combi: [Int], _ relation: [[String]]) -> Bool {
    // combi에 있는 column에 맞추어서 각각의 row의 속성을 합쳐서 string으로 만든다.
    // 그리고 해당 string을 set에 넣어서 중복은 제거한다.
    var set = Set<String>()
    for row in relation {
        var key = ""
        for c in combi {
            key += row[c]
        }
        set.insert(key)
    }
    
    // set의 길이와 row의 길이가 동일하다면 유일성 만족
    return set.count == relation.count
}

func solution(_ relation:[[String]]) -> Int {
    
    // 후보키가 될 수 있는 column의 모든 조합 구하기
        // 최소성 확인을 위해서 길이 순서대로 정렬되도록
    let numOfColumn = relation[0].count
    var combi = [[Int]]()
    for i in 1...numOfColumn {
        combi += combination(Array(0..<numOfColumn), i)
    }

    var ans = [[Int]]()

    // 모든 조합이 각각 후보키가 될 수 있는지 확인
    for c in combi {
        // 최소성 확인
        if !isMinimal(c, ans) { continue }

        // 유일성 확인
        if isUnique(c, relation) { ans.append(c) }
    }

    return ans.count
}

심화: Set과 반복문

위 코드는 최소성 확인을 위해서 key (= [Int])를 집합으로 형변환해서 부분집합이 되는지 판단합니다. 이 형변환을 생략하고 싶다면 key 자체를 [Int]가 아니라 Set해서 풀어도 큰 문제는 없습니다. 예를 들어 key 조합을 구할 때 아래와 같은 코드를 사용하면 될 것입니다.

func combination(_ array: [Int], _ length: Int) -> [Set<Int>] {

    var result = [Set<Int>]()

    func combi(_ now: Set<Int>, _ index: Int) {
        if now.count == length {
            result.append(now)
            return
        }

        for i in index..<array.count {
            combi(now.union([array[i]]), i + 1)
        }

    }

    combi([], 0)

    return result

}

Set도 Collection 자료형이기 때문에 아래처럼 반복문을 사용할 수 있습니다.

var combi: Set<Int> = [1, 2]

for row in relation {
    var key = ""
    for c in combi {
        key += row[c]
    }
    set.insert(key)
}

혹시 set은 순서가 없기 때문에 key를 만들 때 속성의 순서가 꼬이지 않을까, 예를 들면 첫 반복문에서는 “속성1속성2”로 두 번째 반복문에서는 “속성2속성1”처럼 나오지 않을까 걱정하실 수도 있을 것 같습니다.

set이 순서가 없다는 것은 맞습니다. 순서대로 출력을 해보면 insert한 순서와 관계없이 출력되는 것을 볼 수 있습니다. 하지만 한번의 실행에서 여러번 출력을 해도 출력되는 순서는 동일합니다. (다시 실행하면 달라질 수는 있습니다.) 따라서 순서대로 저장되지는 않지만 내부적으로는 순서가 있습니다. (말이 좀 복잡하네요.) 따라서 위와 같은 걱정을 할 필요는 없습니다.

그렇다면 시간 복잡도는 어떨까요? 길이가 N인 Array의 for 문의 경우 O(N)을 보장합니다. 각각의 원소에 index로 접근할 때 O(1)을 보장하기 때문입니다. 길이가 M인 Set의 for문의 경우 대체로 O(M)이라고 합니다. Set의 원소에 접근할 때 O(1)이지만 해시 테이블에 충돌이 있는 경우 최대 O(N)까지 걸릴 수 있기 때문이라고 합니다.

하지만 우리 Set은 길이가 최대 8입니다. 절대절대절대 일어나지 않을 일이라고 가정해도 무방합니다. 따라서 시간 복잡도는 Array를 사용하나 Set을 사용하나 동일하다고 볼 수 있습니다.