Programmers Lv2) 후보키

출처: programmers.co.kr/learn/courses/30/lessons/42890

분류: 카카오 블라인드 2019

---

접근방식

유일성과 최소성을 만족하는 후보키를 찾는 문제입니다.

각 row를 유일하게 식별할 수 있다면 유일성을 만족합니다.
이미 후보키가 포함되어 있다면 최소성을 만족하지 못합니다.

유일성 확인

["a","1","4"]
["2","1","5"]
["a","2","4"]

테이블이 다음과 같이 주어졌고 각 column을 0, 1, 2 라고 할 때,
[0], [1], [2], [1,3] 는 모두 중복을 포함하고 있으므로 유일성을 만족하지 못해 후보키가 될 수 없고,
[0, 1], [1, 2] 는 후보키가 될 수 있습니다.
[1, 2, 3]은 이미 [1, 2]가 포함되어 있으므로 최소성을 만족하지 못해 후보키가 될 수 없습니다.

2차원 배열로 주어지지만 칼럼별로 봐야 하기 때문에 뒤죽박죽... 굉장히 애를 먹었습니다.

저는 칼럼의 인덱스만 가지고 가능한 조합  Combination을 모두 구하고 원소의 개수로 오름차순 정렬한 뒤,

func combinationColumn(relation: [[String]], sholudSelect: Int, current index: Int, selected: [Int], combiList: inout [[Int]]) {
    
    if sholudSelect == 0 {
        combiList.append(selected)
    } else if index == relation[0].count {
        return
    } else {
        var newSelected = selected
        newSelected.append(index)
        combinationColumn(relation: relation, sholudSelect: sholudSelect, current: index+1, selected: selected, combiList: &combiList)
        combinationColumn(relation: relation, sholudSelect: sholudSelect-1, current: index+1, selected: newSelected, combiList: &combiList)
    }
}

각 칼럼 별 row를 모두 붙여서 Set을 만들어서 원소의 개수가 그대로인지 확인하는 방식으로 해결했습니다.

func numberOfRowsSet(of columns: [Int], in relation: [[String]]) -> Int {
    var rows = [String](repeating: "", count: relation.count)
    for col in columns {
        for (idx, row) in relation.enumerated() {
            rows[idx] += row[col]
        }
    }
    return Set(rows).count
}

위의 예에서 [0, 2] 번 조합을 예로 들어보면,

["a4"]
["25"]
["a4"]

와 같이 로우를 모두 붙여서 하나의 칼럼으로 만들고 Set으로 만들었습니다.
그럼 "a4"가 중복되므로 기존의 3개가 아닌 2개로 줄어, 유일성이 깨지게 됩니다.

최소성 확인

이렇게 키를 찾고 나면 다음엔 최소성을 만족하는지 확인해야 합니다.

만약 [1, 4], [0, 2], [1, 2] 의 후보키를 찾았다면,
[1, 2, 3]은 [1, 2]를 포함하고 있기 때문에 최소성을 만족하지 못합니다. 대신 [1, 4], [0, 2]는 문제가 되지 않습니다.

더 똑똑한 방법이 생각나지 않아 일일히 k가 조합에 모두 포함되어 있는지 확인하는 방식으로 해결했네요..

func isUnique(combination com: [Int], keys: Set<[Int]>) -> Bool {
    for key in keys {
        var unique = false
        for k in key {
            if !com.contains(k) {
                unique = true
                break
            }
        }
        if !unique {
            return false
        }
    }
    return true
}

 

해결방법

전체 풀이입니다.

import Foundation

// 칼럼 인덱스 조합 생성
func combinationColumn(relation: [[String]], sholudSelect: Int, current index: Int, selected: [Int], combiList: inout [[Int]]) {
    
    if sholudSelect == 0 {
        combiList.append(selected)
    } else if index == relation[0].count {
        return
    } else {
        var newSelected = selected
        newSelected.append(index)
        combinationColumn(relation: relation, sholudSelect: sholudSelect, current: index+1, selected: selected, combiList: &combiList)
        combinationColumn(relation: relation, sholudSelect: sholudSelect-1, current: index+1, selected: newSelected, combiList: &combiList)
    }
}

// 칼럼을 하나로 합치고 Set의 개수를 확인해 유일성 확인
func numberOfRowsSet(of columns: [Int], in relation: [[String]]) -> Int {
    var rows = [String](repeating: "", count: relation.count)
    for col in columns {
        for (idx, row) in relation.enumerated() {
            rows[idx] += row[col]
        }
    }
    return Set(rows).count
}

// 최소성 확인
func isUnique(combination com: [Int], keys: Set<[Int]>) -> Bool {
    for key in keys {
        var unique = false
        for k in key {
            if !com.contains(k) {
                unique = true
                break
            }
        }
        if !unique {
            return false
        }
    }
    return true
}

func solution(_ relation:[[String]]) -> Int {
    var keys = Set<[Int]>()
    let rowCount = relation.count
    let colCount = relation[0].count
    var combiList = [[Int]]()
    
    for keyCount in 1...colCount {
         combinationColumn(relation: relation, sholudSelect: keyCount, current: 0, selected: [], combiList: &combiList)
    }
    combiList.sort(by: { $0.count < $1.count })
    
    for combi in combiList {
        // 작은것부터 하니까 keys가 combi에 전부 포함되어 있는지만 보면 됨
        guard isUnique(combination: combi, keys: keys) else { continue }
        if numberOfRowsSet(of: combi, in: relation) == rowCount {
            keys.insert(combi)
            // print(keys)
        }
    }
    
    return keys.count
}

 

 

배운점

하 ... 진짜 풀다가 울뻔했습니다... ㅠㅠㅠㅠㅠ

레벨 2인데 너무 어려웠네요... 막 풀다가 결국 다른 분들의 풀이를 참고했습니다. 조합 방식이 제일 잘 이해가 되서 조합으로 풀었고,

비트마스킹 방식으로도 풀 수 있는 것 같아요! 이 방법은 다음에 공부해서 접근해봐야겠습니다 !!!

오늘도 화이팅 🔥