[완전탐색] 후보키 - 2019 KAKAO BLIND RECRUITMENT

해결 방법

i) 테이블의 모든 속성에 대한 조합(Combination)을 구한다.

- 예를 들어, 테이블의 속성 번호를 0, 1, 2, 3으로 매겼을 때, 모든 속성에 대한 조합은 {0, 1, 2, 3, {0, 1}, {0, 2}, {0, 3}, {1, 2}, {1, 3}, {2, 3}, {0, 1, 2}, {0, 1, 3}, {0, 2, 3}, {1, 2, 3}, {1, 2, 3, 4}}가 된다.

- 조합을 C++ 코드로 구현하는 방법은 https://kimcoder.tistory.com/118?category=888042 에 설명했으니 이를 참고하면 된다.

 

ii) 모든 속성 조합에 대하여 유일성을 검증한다.

- 각각의 속성 조합들에 대한 중복 여부를 검증한다.

- 예를 들어, 필자는 ["이름", "전공"] 의 유일성을 검증하기 위해 각 튜블의 이름, 전공에 해당하는 문자열을 합쳐서 중복되는 문자열이 있는지 검증했다.

-> {ryanmusic, apeachmath, tubecomputer, concomputer, muzimusic, apeachmusic} 에서 중복되는 요소는 없기 때문에 유일성이 성립한다.

 

iii) 유일성을 만족한 속성 조합들 중에서 최소성을 만족하지 않는 속성 조합을 제거해나간다.

- 두 속성 조합이 부분 집합 관계라면 한 쪽을 포함하는 집합(조합)은 최소성을 만족하지 않는다.

 

 

소스코드

#include <string>
#include <string.h>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;

vector<vector<int> > unique_vecs;
vector<vector<int> > attr_vecs; // 모든 속성 조합들을 모아둔 벡터
vector<int> column_num_vec;
vector<int> check;

void set_check(int n, int r){
    check.clear();
	for(int i=0;i<r;i++) check.push_back(true);
	for(int i=r;i<n;i++) check.push_back(false);
}

// 조합
void combination(int n){
    vector<int> attr_vec;
	do{
        attr_vec.clear();
		for(int i=0;i<n;i++) if(check[i]) attr_vec.push_back(column_num_vec[i]);
        attr_vecs.push_back(attr_vec);
	} while(next_permutation(check.begin(),check.end()));
}

bool check_minimality(vector<int> a, vector<int> b){
    set<int> union_set;
    for(int i=0;i<a.size();i++) union_set.insert(a[i]);
    for(int i=0;i<b.size();i++) union_set.insert(b[i]);
    int intersection = a.size()+b.size()-union_set.size(); // 교집합의 개수
    // 포함 관계 여부
    if(intersection==a.size()||intersection==b.size()) return false;
    else return true;
}


int solution(vector<vector<string>> relation) {
    int column_size=relation[0].size();
    int row_size=relation.size();
    for(int i=0;i<column_size;i++) column_num_vec.push_back(i); // 0, 1, ... 컬럼의 길이까지 
    for(int i=0;i<column_size;i++) {
        set_check(column_size, i+1);
        sort(check.begin(), check.end());
        combination(column_size);
    }
    
    bool key[column_size]; // 각 속성의 후보키 여부
    set<string> str_set; // 유일성 검사를 위한 set
    for(int i=0;i<attr_vecs.size();i++){
        memset(key, false, sizeof(key));
        str_set.clear();
        for(int j=0;j<attr_vecs[i].size();j++) key[attr_vecs[i][j]]=true; // key_attr에 반영
        for(int j=0;j<relation.size();j++){ // 속성 조합들에 대한 튜플 정보를 문자열로 표현
            string tuple_data="";
            for(int k=0;k<relation[j].size();k++) if(key[k]) tuple_data+=relation[j][k];
            str_set.insert(tuple_data);
        }
        if(str_set.size()!=row_size) continue;
        unique_vecs.push_back(attr_vecs[i]); // 슈퍼키(유일성만 만족)를 저장해둔다.
    }
    
    int answer=unique_vecs.size();
    for(int i=0;i<unique_vecs.size();i++){
        bool minimality = true;
        for(int j=0;j<i;j++) if(!check_minimality(unique_vecs[i], unique_vecs[j])) minimality=false;
        if(!minimality) answer--;
    }
    return answer;
}

 

테스트케이스 28개 모두 정답

 

출처 : https://programmers.co.kr/learn/courses/30/lessons/42890