import Foundation
func solution(_ relation:[[String]]) -> Int {
var uniqueArr: [[Int]] = []
reculsive(relation, [], 0, &uniqueArr) // 유일성을 가지는 모든 경우를 가져온다. (최소성은 체크 안함)
uniqueArr = uniqueArr.sorted (by: { $0.count < $1.count }) // 배열 길이가 작은 순서로 정렬
// 최소성 체크
var index = 0
var removeIndex = Set<Int>() // 앞으로 지울 인덱스들
while uniqueArr.count > index + 1 {
let unique = uniqueArr[index]
index += 1
for searchIdx in index..<uniqueArr.count {
let searchArr = uniqueArr[searchIdx]
var containAll = true
for arg in unique {
if !searchArr.contains(arg) { // 컬럼값 하나라도 없다면 통과
containAll = false
break
}
}
if containAll {
removeIndex.insert(searchIdx)
}
}
}
// 한번에 촤르륵 지운다.
let removeList = Array(removeIndex).sorted(by: >)
removeList.forEach { uniqueArr.remove(at: $0) }
return uniqueArr.count
}
func reculsive(_ relation:[[String]],
_ visiteColumIndexs: [Int],
_ startIndex: Int,
_ uniqueArr: inout [[Int]]) {
let rowCount = relation.count
let columCount = relation[0].count
for index in startIndex..<columCount {
var newVisiteColumIndexs = visiteColumIndexs
newVisiteColumIndexs.append(index)
var sets = Set<String>()
for row in relation {
let str = newVisiteColumIndexs.map { "\(row[$0])" }.reduce("") { $0 + $1 }
sets.insert(str)
}
if sets.count == rowCount { // 유일성 만족
uniqueArr.append(newVisiteColumIndexs)
} else {
reculsive(relation, newVisiteColumIndexs, index + 1, &uniqueArr)
}
}
}
생각보다 고전한 문제.
유일성을 가지는 모든 경우의 수는 재귀를 통해 전부 탐색했고
최소성을 체크는 하나하나 씩 순대서로 지울 컬럼들을 모두 탐색한 후
한 번에 촤르르륵 지웠다. (루프문 도중에 지울 수가 없기 때문)
별거 아닌 문제였는데 오늘따라 머리가 안돌아갔나...