[Swift Algorithm] 프로그래머스 42890 후보키 (2019 카카오 블라인드)

 

programmers.co.kr/learn/courses/30/lessons/42890

코딩테스트 연습 - 후보키

 

풀이과정

처음에 보고 해결방법으로 든 생각이

속성의 조합으로 먼저 나열하고 그 조합마다 빼내와서 비교하면 될것 같아보였어요

[학번, 이름]과 [이름, 학번]은 같은 값에 해당하구요

 

[학번], [이름], [전공], [학년] -> 4

[학번,이름], [학번,전공], [학번,학년], [이름,전공], [이름,학년], [전공, 학년] -> 6

[학번,이름,전공], [학번,이름,학년], [이름,전공,학년], [학번,전공,학년] -> 4

[학번,이름,전공,학년] -> 1

총 15개의 조합이 나오네요

4개의 부분집합은 16개인데 공집합을 빼면 15개가 될거에요

 

각각 파싱해서 예를 들면

[학번, 이름]에 해당하는 데이터들을 합쳐서 Set에 넣고

다 넣었을때 후보키라면 데이터 모두 구분할 수 있어야겠죠?

따라서 Set의 size와 데이터의 row의 크기가 같아야해요

 

이런 방법으로 생각 하다가

비효율적인것 같아서 효율적인 방법을 찾았는데

비트마스크를 이용한 풀이가 있더라구요

 

부분집합이니까..! 비트마스크를 쓰는게 더 뭔가 빠를거 같은 느낌이 들었어요

파싱부분이 안들어가니까 시간도 덜 소모될것 같았어요

 

비트마스크 방법으론

학번	이름	전공	학년
1	0	0	0
0	1	0	0
0	0	1	0
0	0	0	1
1	1	0	0

 

1000 -> [학번]

0100 -> [이름]

1100 -> [학번,이름]

1이 켜진 속성을 비교하는 식으로 계산하는거에요

공집하는 제외하고

속성마다 비트자리를 보면

4자리로 2의 4승은 15개가 되겟네요

 

문제보기와같이 속성이 4개인경우

접근할 속성 1...15은  1...1<<columnSize(columnSize는 4) 와 같구요 

 

현재 켜진 비트의 데이터를 비교해야하니까

데이터 row에 접근하고

해당 row의 켜진 비트의 데이터를 모두 더해서 겹치는게 있는지 비교해주는 방식이에요

 

처음의 방법이랑은 비슷한 논리지만 비트마스크를 쓰는 방식이 더 간단해 보였어요

 

func solutionP42890(_ relation:[[String]]) -> Int {
    
    let columnSize = relation[0].count
    let rowSize = relation.count
    var combiSet = Set<String>()
    var resultSet = Set<Int>()
    
    // 접근할 속성bit
    for bit in 1..<(1<<columnSize) {
        combiSet.removeAll()
        // 데이터 전체 접근
        for r in 0..<rowSize {
            // 데이터 속성 접근
            var tempString = ""
            for c in 0..<columnSize {
                // 1로 켜진속성만 접근
                if (bit & (1<<c)) != 0 {
                    tempString += relation[r][c]
                }
            }
            combiSet.update(with: tempString)
        }
        if combiSet.count == rowSize {
            var isSkip = false
            for value in resultSet {
                if (value & bit) == value {
                    isSkip = true
                    break
                }
            }
            
            if isSkip {
                continue
            }
            resultSet.update(with: bit)
        }
    }
//    print(resultSet)
    return resultSet.count
}