22.04.17. 풀었던 문제들

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();
}