[프로그래머스] 2019 KAKAO BLIND RECRUITMENT 후보키 with Swift

안녕하세요. 오늘은 프로그래머스 후보키 문제를 풀어보겠습니다!

후보키 문제는 여러가지 알고리즘을 섞어만든 문제인데요!

 

코딩테스트 연습 - 후보키

 

row&column이 max 8*20이기 때문에 어떤 방법으로해도 전략만 잘 세운다면 시간초과날 일은 없을듯합니다!

 

처음에는 재귀알고리즘을 이용하여 combination을 하여 후보키 후보조합을 만들어줍니다!

 

이 후 sort를 해줬는데요.

 

sort의 이유는 최소성을 만족하는 후보키를 검증하는 과정에서 앞에서 이미 후보키가 되었다면, 뒤에서는 해당키를 포함하는지(&연산자 활용) 확인하면 알 수 있기 때문입니다.

 

그 이후에 유일성 확인을 해주는데요.

 

각각의 데이터에 대하여 집합을 만들어 확인하기보다는 Dictionary로 유일성을 검증하는 편이 좋을듯하여 알고리즘을 구성하였습니다.

 

모든 예외상황은 통과하면 answerSet에 append하여 answerSet의 count를 return해주면 문제가 해결됩니다.

 

import Foundation

var combinationSet:[[Int]] = [[Int]]()
var currentSet:[Int] = [Int]()
func makeCombinationSet(_ currentDepth:Int, _ count:Int) {
    if currentDepth == count {
        if currentSet == [] {
            return
        }
        combinationSet.append(currentSet)
        return
    }
    
    currentSet.append(currentDepth + 1)
    makeCombinationSet(currentDepth + 1, count)
    currentSet.remove(at: currentSet.count - 1)
    makeCombinationSet(currentDepth + 1, count)
    
    
}

func solution(_ relation:[[String]]) -> Int {
    
    let count = relation[0].count
    makeCombinationSet(0, count)
    combinationSet.sort(by: {$0.count < $1.count})
    
    var answerSet:[Int] = [Int]()
    
    combinationLoop : for combination in combinationSet {
        var currentAnswer = 0
        for i in combination {
            currentAnswer += (1 << i)
        }
        
        for answer in answerSet {
            if answer&currentAnswer == answer {
                continue combinationLoop
            }
        }
        
        var dictionary:[String:Int] = [String:Int]()
        for relationShip in relation {
            var dicionaryKey = ""
            for i in combination {
                dicionaryKey += relationShip[i-1]
            }
            if dictionary[dicionaryKey] == 1 {
                continue combinationLoop
            }
            dictionary[dicionaryKey] = 1
        }
        answerSet.append(currentAnswer)
    }
    
    return answerSet.count
}

 

오늘은 여기까지이며, 질문이 있으시면 댓글로 남겨주세요☺️

 

오늘도 좋은 하루 되세요!