[프로그래머스 / swift] 2019 KAKAO BLIND RECRUITMENT - 후보키

프로그래머스

문제 설계

조합을 이용해서 풀어야겠다는 생각, 그 이후로 비교를 하면서 후보키의 개수를 정해야겠다는 생각까지만 했고 어떻게 설계해야 할지 전혀 감이 오지 않았다. 뭔가 알 거 같은데 제대로 떠오르지는 않는...

 

문제 풀이 (정답) - 직접 푼 풀이 아님

import Foundation

// 주어진 릴레이션에서 후보키의 최대 개수를 찾는 함수
func solution(_ relation: [[String]]) -> Int {
    let rows = relation.count // 릴레이션의 행 개수
    let cols = relation[0].count // 릴레이션의 열 개수
    
    var candidateKeys: [[Int]] = [] // 후보키를 저장할 배열
    
    // 조합을 이용해 모든 키 조합을 생성하는 함수
    func combinations(_ arr: [Int], _ length: Int) -> [[Int]] {
        if length == 0 { return [[]] } // 길이가 0인 경우 빈 배열 반환
        if arr.isEmpty { return [] } // 입력 배열이 빈 경우 빈 배열 반환
        
        var result: [[Int]] = []
        let rest = Array(arr[1..<arr.count]) // 첫 번째 요소를 제외한 나머지 배열
        
        // 첫 번째 요소를 포함한 조합
        for comb in combinations(rest, length - 1) {
            result.append([arr[0]] + comb)
        }
        
        // 첫 번째 요소를 포함하지 않은 조합
        result += combinations(rest, length)
        
        return result
    }
    
    // 유일성 체크 함수
    func isUnique(_ indices: [Int]) -> Bool {
        var seen = Set<String>() // 키 조합을 저장할 집합
        for row in relation {
            // 주어진 인덱스의 값을 조합하여 키 문자열 생성
            let key = indices.map { row[$0] }.joined(separator: ",")
            if seen.contains(key) { // 이미 키가 집합에 있으면 유일성 실패
                return false
            }
            seen.insert(key) // 집합에 키 추가
        }
        return true
    }
    
    // 최소성 체크 함수
    func isMinimal(_ indices: [Int]) -> Bool {
        for candidate in candidateKeys {
            // 현재 키 조합이 이미 발견된 후보키의 부분집합인 경우 최소성 실패
            if Set(candidate).isSubset(of: Set(indices)) {
                return false
            }
        }
        return true
    }
    
    let allIndices = Array(0..<cols) // 모든 인덱스의 배열
    
    // 각 길이에 대해 가능한 모든 조합을 생성하고 검사
    for length in 1...cols {
        let combs = combinations(allIndices, length) // 길이가 length인 모든 조합
        for comb in combs {
            if isUnique(comb) && isMinimal(comb) { // 유일성과 최소성을 모두 만족하면
                candidateKeys.append(comb) // 후보키로 추가
            }
        }
    }
    
    return candidateKeys.count // 후보키의 개수 반환
}

정리

1. let key = indices.map { row[$0] }.joined(separator: ",")

이 코드는 indices 배열에 따라 row 배열에서 특정 인덱스의 값을 추출하고, 추출된 값들을 ","로 구분하여 하나의 문자열로 합치는 역할을 합니다.

- indices.map { row[$0] }:
- indices는 인덱스들의 배열입니다. map 함수는 배열의 각 요소에 대해 주어진 클로저를 적용합니다.
- { row[$0] }는 클로저로, indices 배열의 각 인덱스를 사용하여 row 배열의 해당 값을 가져옵니다.
- 결과는 indices 배열의 각 인덱스에 해당하는 row 배열의 값을 모은 새로운 배열입니다.

- .joined(separator: ","):
- map 함수의 결과로 얻어진 배열의 요소들을 "," 구분자로 합쳐 하나의 문자열로 만듭니다.

let row = ["100", "ryan", "music", "2"]
let indices = [0, 2]

let key = indices.map { row[$0] }.joined(separator: ",")
// indices.map { row[$0] }는 ["100", "music"]이 되고,
// .joined(separator: ",")는 "100,music"이 됩니다.

print(key) // 출력: "100,music"

2. if Set(candidate).isSubset(of: Set(indices))

이 코드는 candidate 배열이 indices 배열의 부분집합인지 확인합니다.

- Set(candidate):
- candidate 배열을 집합(Set)으로 변환합니다.
- 집합은 중복된 요소를 허용하지 않으며, 요소들의 순서는 중요하지 않습니다.

- isSubset(of: Set(indices)):
- candidate 집합이 indices 집합의 부분집합인지 확인합니다.
- 부분집합이라는 것은 candidate의 모든 요소가 indices에 포함되어 있다는 의미입니다.

let candidate = [1, 2]
let indices = [1, 2, 3]

if Set(candidate).isSubset(of: Set(indices)) {
    print("candidate는 indices의 부분집합입니다.")
} else {
    print("candidate는 indices의 부분집합이 아닙니다.")
}

// 출력: candidate는 indices의 부분집합입니다.

 

3. 빈 집합 초기화

var s: Set<Int> = Set()
// 또는
var s = Set<Int>()

 

4. 배열 생성

let cols = 4
let allIndices = Array(0..<cols)

print(allIndices)  // 출력: [0, 1, 2, 3]