1. 후보키
- key의 조합을 고른다. 이 조합은 nC1, nC2, ... , nCn으로 뽑을 수 있는 모든 경우의 수이다.(여기서 n은 key의 개수)
- 위에서 고른 key들로 유일성을 만족하는지 검사한다. (키에 해당하는 relation의 개수가 중복이 없는지) - set으로 검사하면 된다.
- 위 두 조건을 만족하는 것 중 포함관계가 있는지 검사하면 된다.
// 후보키
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <queue>
using namespace std;
// keys에 해당하는 key들이 unique한지 검사하는 함수
bool isUnique(string keys, vector<vector<string>>& relation){
sort(keys.begin(), keys.end());
set<string> s;
int num_rows = relation.size(), num_keys = keys.length();
for(int i = 0; i<num_rows; i++){
string temp_key = "";
for(int k = 0; k<num_keys; k++){
temp_key += relation[i][stoi(keys.substr(k, 1))];
}
s.insert(temp_key);
}
if(s.size() != num_rows) return false;
else return true;
}
// 조합 뽑아주는 함수
void combination(int curD, int maxD, int prevIdx, int maxIdx, string key, vector<bool> &isUsed, vector<string> &keyList){
if(curD == maxD){
keyList.push_back(key);
return;
}
for(int i = prevIdx + 1; i<maxIdx; i++){
isUsed[i] = true;
combination(curD + 1, maxD, i, maxIdx, key + to_string(i), isUsed, keyList);
isUsed[i] = false;
}
}
int solution(vector<vector<string>> relation) {
int num_keys = relation[0].size();
vector<bool> isUsed(num_keys, false);
vector<string> keyList;
for(int i = num_keys-1; i>=0; i--){
combination(0, i + 1, -1, num_keys, "", isUsed, keyList);
}
// keyList : 가능한 key의 조합
map<string, int> m;
for(int i = 0; i<keyList.size(); i++){
m[keyList[i]] = isUnique(keyList[i], relation);
//cout<<keyList[i]<<" "<<m[keyList[i]]<<endl;
}
queue<string> q;
string maxKey = "";
for(int i = 0; i<num_keys; i++){
maxKey += to_string(i);
} q.push(maxKey);
// 어떤 key가 uniqueness를 만족하지만 그 key에서 1개라도 뺀 것이 uniqueness를 만족하면 minimality를
// 만족하지 못하는 것. 이를 검사한다.
set<string> s;
while(!q.empty()){
string frontKey = q.front(); q.pop();
bool isMinimal = true;
for(int i = 0; i<frontKey.length(); i++){
string downKey = frontKey.substr(0, i) + frontKey.substr(i + 1, frontKey.length() - i - 1);
if(m[downKey]){
isMinimal = false;
q.push(downKey);
}
}
if(frontKey.size() == 1 || isMinimal) s.insert(frontKey);
}
return s.size();
}
'PS > PS Log' 카테고리의 다른 글
22.04.20. 풀었던 문제들 (0) | 2022.06.23 |
---|---|
22.04.19. 풀었던 문제들 (0) | 2022.06.23 |
22.04.16. 풀었던 문제들 *** KMP 알고리즘 (0) | 2022.06.23 |
22.04.15. 풀었던 문제들 (0) | 2022.06.23 |
22.04.09. 풀었던 문제들 (0) | 2022.06.23 |