프로그래머스 - 후보키 (Lv.2)

OQ·2022년 4월 2일
0

프로그래머스

목록 보기
31/33

문제 링크

풀이

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)
        }
    }
}

후기

생각보다 고전한 문제.
유일성을 가지는 모든 경우의 수는 재귀를 통해 전부 탐색했고
최소성을 체크는 하나하나 씩 순대서로 지울 컬럼들을 모두 탐색한 후
한 번에 촤르르륵 지웠다. (루프문 도중에 지울 수가 없기 때문)

별거 아닌 문제였는데 오늘따라 머리가 안돌아갔나...

profile
덕업일치 iOS 개발자

0개의 댓글