3번 문제는 정답률이 확 떨어지는 만큼 까다로운 문제입니다. 문제는 후보키를 구하는 문제인데, 후보키는 유일성과 최소성을 만족해야 한다고 합니다. 즉, A가 후보키라면 AB, AC는 후보키가 될 수 없다는 뜻이 됩니다.
여기서 집합의 원리를 비트연산자를 이용해 구현할 수 있습니다. i 번째 원소가 후보키 집합의 원소라면 1, 아니라면 0으로 비트를 설정한 숫자가 있을 때, 최소성을 가지는 가지는 수는 다른 후보키와 AND 연산을 했을 때 자기 자신이 나오게 됩니다.
좀 더 자세히 설명하면, 1(0001) 과 3(0011) 이 있을 때, $ 1&3 = 1$ 이므로, 1이 최종적인 후보키가 됨을 알 수 있습니다.
i번째 튜플이 후보키 집합에 포함 되냐 되지 않느냐를 체크해야 하는데, 튜플의 개수는 8개이므로 $2^8$ 가지만 체크해보면 됩니다. 즉, 모든 경우의 수를 빠르게 체크할 수 있습니다.
그러므로 i번째 원소가 포함 되는 경우, 안 되는 경우를 재귀함수로 구현하여 호출하면서, 후보키 후보가 나왔을 때 비트 연산자를 통하여 최소성을 만족하면 정답이 됩니다. 최종적으로 그런 후보키들을 저장하고 있는 배열의 크기를 반환합니다.
※해당 소스코드는 참고용이며, 최적화 된 공식 솔루션 소스가 아닙니다. 이 소스를 그대로 복사하여 이용, 또는 제출하는 행위에 대한 불이익은 책임지지 않습니다.
#include <string>
#include <set>
#include <vector>
using namespace std;
vector<int> cdt;
void dfs(int idx, int bit, vector<vector<string> > &relation) {
if (idx == relation[0].size()) {
return;
}
set<string> cmp;
for (int i = 0; i<relation.size(); i++) {
string key;
for (int j = 0; j<relation[i].size(); j++) {
if ((bit & (1 << j))) {
key += relation[i][j];
}
}
cmp.insert(key);
}
if (cmp.size() == relation.size()) {
bool f=true;
for (int i = 0; i<cdt.size(); i++) {
if ((cdt[i] & bit) == cdt[i]) {
f=false;
break;
}
if ((cdt[i] & bit) == bit) {
f=false;
cdt[i] = bit;
break;
}
}
if(f) {
cdt.push_back(bit);
}
}
dfs(idx + 1, bit, relation);
dfs(idx + 1, (bit | (1 << (idx + 1))), relation);
}
int solution(vector<vector<string>> relation) {
dfs(0, 0, relation);
dfs(0, 1, relation);
return cdt.size();
}