Level 2. 후보키

Level 2. 후보키

 

 

카카오 문제 답게 하나의 개념만 물어보지 않고, 조합과 중복 체크 등 여러 개념을 물어보는 문제였다.

• 그래서 카카오 문제를 풀고 나면 항상 함수가 많다..

 

처음에 해시 값을 계산해 중복을 체크할 때, 각 속성 값의 해시 값을 더해 계산해서 오답 처리되었다.

• (2, 3)과 (3, 2)가 같은 것으로 처리되었기 때문이다.

 

각 속성들을 하나의 문자열로 합친 후 해시 값을 계산해 해결했다.

 

최소성의 경우 적은 수의 조합부터 후보키가 가능한지 검사하고, bitset과 교집합(&)을 이용해 확인했다.

 

#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_set>
#include <utility>
#include <bitset>

using namespace std;
using bset = bitset<8>;

vector<vector<bool>> get_comb(int n, int r)
{
    vector<vector<bool>> result;
    vector<bool> comb(n, 0);

    fill_n(comb.rbegin(), r, 1);

    do
        result.emplace_back(comb);
    while (next_permutation(comb.begin(), comb.end()));

    return result;
}

bset to_bitset(vector<bool>& v)
{
    bset bs;

    for (int i = 0; i < v.size(); ++i)
        bs.set(i, v[i]);

    return bs;
}

bool satisfy_minimality(vector<bset>& candidates, vector<bool>& comb)
{
    bset bsA = to_bitset(comb);

    for (bset& bsB : candidates)
        if ((bsA & bsB) == bsB)
            return false;

    return true;
}

bool is_candidate(vector<vector<string>>& relation, vector<bool>& comb)
{
    unordered_set<size_t> uset;
    hash<string> hashFunc;

    for (vector<string>& record : relation)
    {
        string hashKey;

        for (int i = 0; i < comb.size(); ++i)
            hashKey += (comb[i]) ? record[i] : "";

        uset.emplace(hashFunc(hashKey));
    }

    return uset.size() == relation.size();
}

int solution(vector<vector<string>> relation)
{
    const int ROW = relation.size(), COL = relation.front().size();
    vector<bset> candidates;

    for (int r = 1; r <= COL; ++r)
        for (vector<bool>& comb : get_comb(COL, r))
            if (satisfy_minimality(candidates, comb) && is_candidate(relation, comb))
                candidates.emplace_back(to_bitset(comb));

    return candidates.size();
}