프로그래머스 - 후보키

내 풀이

import Foundation

func solution(_ relation:[[String]]) -> Int {
    let colCount = relation[0].count
    let rowCount = relation.count
    var combinations = [[Int]]()
    var uniqueSet = Set<Set<Int>>()
    
    // 모든 컬럼 부분 집합 구하기
    for i in 1..<(1<<colCount) {
        var curr = [Int]()
        for j in 0..<colCount {
            if (i & (1<<j)) > 0 {
                curr.append(j)
            }
        }
        combinations.append(curr)
    }
    
    // 각 부분 집합마다 후보키 가능 여부 확인 - 유일성 검사
    for comb in combinations {
        var currSet = Set<String>()
        for row in 0..<rowCount {
            var currStr = ""
            for col in comb {
                let colIndex = Int(col)
                currStr.append(relation[row][colIndex])
            }
            currSet.insert(currStr)
        }
        // 중복 튜플 있는지 검사 (유일성)
        if currSet.count == rowCount {
            uniqueSet.insert(Set(comb))
        }
    }
    
    // 최소성 검사
    for s in uniqueSet {
        for comp in uniqueSet {
            if s.isSuperset(of: comp) && s != comp {
                uniqueSet.remove(s)
            }
        }
    }
    
    return uniqueSet.count
}

조합을 구하는 효율적인 방법이 있을까 고민하다가 모르겠어서 공식 해설을 참고했다. 일단 모든 어트리뷰트의 부분 집합을 구한 다음 후보 키가 될 수 있는지 검사하는 식으로 문제를 풀면 되는 것 같다.

풀이 과정

1. 비트 연산을 이용해 모든 어트리뷰트의 부분 집합을 구한다.
2. 1번에서 얻은 조합들을 하나씩 순회하면서 중복되는 튜플이 없는지 확인한다. 중복을 쉽게 검사하기 위해 Set 를 사용했다. (유일성 검사)
3. 유일성 검사를 통과한 조합 중 최소성을 만족하지 못하는 조합은 제거한다. 즉, 어떤 집합의 슈퍼셋이 되는 집합은 제거한다.

해설을 보니 풀이 과정은 금방 이해가 갔는데 집합 비교, 중복 제거, 삭제 연산 등을 간단하게 하려고 Set을 많이 사용하고 또 Set 안에 Set을 넣고 하다보니 코드를 짜다가도 많이 헷갈렸던 것 같다. 😅

새로 배운 내용

• 입력 데이터의 수가 적으면 일단 모든 경우를 다 확인하는 방법으로 문제를 풀어야 할 것 같다. 무조건 효율적인 방법을 쓰려고 너무 고민하지 말자.
• 비트 연산으로도 부분 조합을 구할 수 있다.
  • 1<<n : 원소가 n개일 때 모든 부분 집합의 수
  • i & (1 << j) : i의 j번째 비트가 1인지 검사

참고한 링크

• 카카오 공식 해설
• 파이썬 풀이
• 비트 연산자로 조합 구하기
• 비트 연산자로 조합 구하기 2

다른 사람의 풀이

import Foundation

func solution(_ relation:[[String]]) -> Int {
    let rowSize = relation.count
    let colSize = relation[0].count

    var resultSet = Set<Int>()

    for bit in 1..<(1<<colSize) {
        var combiSet = Set<String>()
        var isUnique = true

        for r in 0..<rowSize {
            var tmpStr = "" 
            for c in 0..<colSize where (bit & (1<<c)) != 0 { 
                tmpStr += relation[r][c] 
            } 
            if combiSet.update(with: tmpStr) != nil { // set내에 중복 요소 존재
                isUnique = false
                break
            }
        } 

        if isUnique && resultSet.filter{ ($0 & bit) == $0 }.isEmpty {
            resultSet.insert(bit)
        } 
    }

    return resultSet.count 
}

비트 연산을 잘 활용하신 것 같다. 존경스럽다……