이번문제는 후보키 문제였다..
학교에서 데이터베이스시스템 설계가 A+인데도, 이문제를 볼때 어? 이거 후보키 최소성을 왜 이런식으로 만족을 하지? 라는생각이 들었다.
그래서 후보키를 뽑는 과정을 살펴보자면,
[["100","ryan","music","2"],["200","apeach","math","2"],["300","tube","computer","3"],["400","con","computer","4"],["500","muzi","music","3"],["600","apeach","music","2"]]
자 이런식의 릴레이션이 있다면,
학번: 100,200,300,400,500
이름: ryan,apeach,tube,con,muzi,apeach
전공: music,math,computer,computer,music,music
학년: 2,2,3,4,3,2
이런식으로 설정이 될것 입니다.
유일성을 만족하기위해서는
학번이 있겠네요 나머지 칼럼에서는 겹치는게 있으니깐요
그러면 다른 유일성을 만족시키는 경우를 보자면
학번,이름
학번,전공
학번,학년
전부 유일성을 만족시키네요
그러나 이건 최소성을 만족시키지 못합니다. 이미 학번하나가 후보키로 존재하기 때문이죠
이름,전공 이런건 후보키를 만족합니다.
결국 이 문제는 2가지 로직으로 수행이 되야합니다.
1. 유일성을 만족시키는 조합 찾기
2. 1번 조합에서 최소성을 만족시키는 조합 찾기
이 2가지를 확인해 봐야합니다.
우선 Map 부터 만들어봅시다.
학번: 100,200,300,400,500
이름: ryan,apeach,tube,con,muzi,apeach
전공: music,math,computer,computer,music,music
학년: 2,2,3,4,3,2
이런식으로 Map을 만드는 과정입니다.
void makeMap(vector<vector<string>> & relation){
for(int i=0;i<k;i++){
for(int j=0;j<relation.size();j++){
string temp = relation[j][i];
map[i].push_back(temp);
}
}
}이런식으로 하면 이제 map에서
'[0]: 100,200,300,400,500
'[1]: ryan,apeach,tube,con,muzi,apeach
'[2]: music,math,computer,computer,music,music
'[3]: 2,2,3,4,3,2
이런식으로 만들어 지겠네요
그다음에 모든 조합을 구해야하니까 do while을 돌려줍니다.
이러면
0
1
2
3
01
02
03
12
13
23
012
013
123
0123
이런식으로 확인할 것입니다.
그래서 이 모든 조합에서 유일성을 만족하는지 부터 확인하는겁니다.
do{
vector<int>tmp;
for(int j =0;j<r;j++){
tmp.push_back(v[j]);
}
sort(tmp.begin(),tmp.end());
string A="";
for(int i=0;i<tmp.size();i++){
A+=to_string(tmp[i]);
}
int ssize=s.size();
s.insert(A);
int sssize=s.size();
if(ssize!=sssize){
if(mycheck(tmp)){
int tcheck=0;
for(int i=0;i<Only.size();i++){
int Osize=Only[i].size();
int tsize=0;
for(int j=0;j<tmp.size();j++){
if(Only[i].find(tmp[j])!=string::npos){
tsize++;
}
}
if(tsize==Osize){
tcheck++;
break;
}
}
if(tcheck==0){
string xx="";
for(int k=0;k<tmp.size();k++){
xx+=tmp[k];
}
cout<<xx<<" ";
Only.push_back(xx);
}
}
}
reverse(v.begin()+r,v.end());
}while(next_permutation(v.begin(),v.end()));여기 dowhile문을 보면
tmp에 이제 아까 위에서 설명했던 0,1,2,3,[0,1],[0,2],,,이런식으로 들어가게됩니다.
그리고 유일성을 mycheck에서 확인합니다.
bool mycheck(vector<int> & t){
set<string>s;
vector<string>temp;
for(int i=0;i<c;i++){
for(int j=0;j<t.size();j++){
string a = map[t[j]][i];
temp.push_back(a);
}
string x="";
for(int z=0;z<temp.size();z++){
x+=temp[z];
}
temp.clear();
int ssize = s.size();
s.insert(x);
int sssize = s.size();
if(sssize==ssize){
return false;
}
}
return true;
}여기에서 보면 for문을 돌면서 temp에다가 넣습니다.
만약에 tmp에 0과1이 들어있다 하죠
그러면 2중포문에서 내부의 for문을 다돌면
temp에는 100 ryan이 있을것입니다.
이걸 string x 로 하나로 만들어 100ryan이 되고
temp를 비워주고(다음 바깥for문돌때 새롭게 만들어야하니까)
그다음에 set에 넣어줍니다.
그다음 바깥 for문에서는 그다음 칼럼에 해당하는
200apeach가 됩니다.
만약에 100ryan이 다음에 또 들어오면 set의 size가 변하지 않기 때문에, 이제 return false를
for문을 전부 돌았다면 유일성을 만족시키니 true를 반환합니다.
그다음은 이제 최소성 만족을 확인해야합니다.
if(mycheck(tmp))의 내부를 보면
제가 이문제를 푸는데 2틀이상 걸렸는데 그이유가
저는 처음에 set을 사용하여 동일하게 02가 유일성을 만족하여 set에 들어있다고 가정,
만약에 023이 들어오면 string.find함수를 활용하여 이제, 02가있으면 최소성 만족 x
이런로직이었는데
여기서 생기는 오류가
02가 set에 들어있고 만약 012가 들어오면 이걸 잡아낼수가 없다는것입니다. 왜? 012는 02가 안붙어있으니까
그래서, 이걸 0과 2 각각 찾아서 확인해줘야합니다.
int tcheck=0;
for(int i=0;i<Only.size();i++){
int Osize=Only[i].size();
int tsize=0;
for(int j=0;j<tmp.size();j++){
if(Only[i].find(tmp[j])!=string::npos){
tsize++;
}
}
if(tsize==Osize){
tcheck++;
break;
}
}
if(tcheck==0){
string xx="";
for(int k=0;k<tmp.size();k++){
xx+=tmp[k];
}
cout<<xx<<" ";
Only.push_back(xx);
만약에 Only(최소성도 만족하는 후보키)에 012와 023이 들어있다고 칩시다.
그러고 tmp에는 0123이 들어있다고 가정하면
Only에서 012를 하나 가져옵니다.
그다음에 tmp에 해당하는 0,1,2,3각각 Only[i]번째에 해당하는 012와 각각 비교를 합니다. 그러면 tsize가 3이 됩니다.
만약 tsize가 ONly[i]의 size와 동일하다면 최소성을 만족하지 못합니다. 그러므로 tcheck++하고 break를 합니다.
break를 하는 이유는 012에서 최소성을 만족시키지 못했다면 다음 Only 후보키인 023을 확인 할 이유가 없기 때문입니다.
고로 tcheck가 0이라는것은 최소성도 만족한다는 뜻이고 Only에다가 넣어줍니다.
그다음에 최종적으로 Only의 크기를 반환하면 정답이 됩니다.
정답 CODE
#include <string>
#include <vector>
#include <iostream>
#include <set>
#include <algorithm>
using namespace std;
int k = 0;
int c = 0;
vector<string>map[21];
void makeMap(vector<vector<string>> & relation){
for(int i=0;i<k;i++){
for(int j=0;j<relation.size();j++){
string temp = relation[j][i];
map[i].push_back(temp);
}
}
}
bool mycheck(vector<int> & t){
set<string>s;
vector<string>temp;
for(int i=0;i<c;i++){
for(int j=0;j<t.size();j++){
string a = map[t[j]][i];
temp.push_back(a);
}
string x="";
for(int z=0;z<temp.size();z++){
x+=temp[z];
}
temp.clear();
int ssize = s.size();
s.insert(x);
int sssize = s.size();
if(sssize==ssize){
return false;
}
}
return true;
}
int solution(vector<vector<string>> relation) {
int answer = 0;
k=relation[0].size();
makeMap(relation);
c=map[0].size();
vector<int> v;
vector<string> Only;
for(int i=0;i<k;i++){
v.push_back(i);
}
set <string> s;
for(int i=1;i<=k;i++){
int n = v.size();
int r = i;
do{
vector<int>tmp;
for(int j =0;j<r;j++){
tmp.push_back(v[j]);
}
sort(tmp.begin(),tmp.end());
string A="";
for(int i=0;i<tmp.size();i++){
A+=to_string(tmp[i]);
}
int ssize=s.size();
s.insert(A);
int sssize=s.size();
if(ssize!=sssize){
if(mycheck(tmp)){
int tcheck=0;
for(int i=0;i<Only.size();i++){
int Osize=Only[i].size();
int tsize=0;
for(int j=0;j<tmp.size();j++){
if(Only[i].find(tmp[j])!=string::npos){
tsize++;
}
}
if(tsize==Osize){
tcheck++;
break;
}
}
if(tcheck==0){
string xx="";
for(int k=0;k<tmp.size();k++){
xx+=tmp[k];
}
cout<<xx<<" ";
Only.push_back(xx);
}
}
}
reverse(v.begin()+r,v.end());
}while(next_permutation(v.begin(),v.end()));
}
return Only.size();
}