2019 KAKAO BLIND RECRUITMENT: 후보키 (with Swift)

풀면서 이게 맞게 풀고 있는 것인가 라는 생각이 많이 들었던 문제이다.

입력의 크기가 매우 작은 만큼, 시간이 오래 걸리는 로직이더라도 시간초과 없이 잘 통과한 것 같다.

 

 

로직은 아래와 같다.

column의 수가 n개일 때, 우리가 후보키인지 확인할 수 있는 col 조합은 총 2^n가지이다.

이들 전부를 dfs()를  통해 구하고, 각 case마다 check()함수를 통해 

해당 조합이 후보키가 될 수 있는지 체크한다.

 

후보키가 될 수 있는지 체크하는 방식은

( 1,3,7)번 column에 대해서 확인하는 것이라면,

relation의 모든 행에 대해 1,3,7번 column만 걸러내 [(relation[0][1], relation[0][3], relation[0][7]), relation[1][1], relation[1][3], relation[1][7]) ...... ]

과 같이 배열을 구성하고,

이를 Set으로 바꿔어 중복되는 요소를 걸러내준다.

Array와 이를 Set으로 바꾼 것의 길이가 같다면, 중복되는 요소가 없다는 것이므로, 후보키 후보가 될 수 있다는 것이다. ( 최소성은 나중에 확인해봐야함)

 

이런 경우에만 hubokey라는 배열에 (1,3,7)과 같은 Set을 추가해준다.

이렇게 "최소성"을 제외했을 때 후보키들을 모두 모아놓고나면,

2중 for문을 돌려 모든 후보키 후보들에 대하여 본인의 subset이 몇 개 존재하는지 체크해본다.

본인의 subset이 2개 이상( 본인 1개 이외의 subset이 존재한다는 뜻)이라면, 이는 "최소성"을 만족하지 않는 것이므로, pass해주고,

subset이 1개(자기 자신)인 것들에 대해서만 result에 1을 더해준다.