후보키[프로그래머스]

DFS 접근법:

DFS 를 통해 만들수 있는 후보키의 조합을 모두 생성한다.
만들어진 조합을 순회하며 최소성과 유일성을 만족하는지 확인한다.
1. 조합을 미리 문자열 크기대로 오름차순 정렬했기 때문에 순서대로 테스트 할수 있다.
2. 지금의 조헙이 이미 추가된 최소성과 유일성이 만족된 후보키에 요소라면 최소성을 만족 못했다.
3. 그다음 Set STL을 통해서 각 조합으로만든 데이터들의 중복이 확인하여 유일성을 검사한다.
후보키들의 사이즈를 리턴한다.

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

bool checkMinimality(string current_comb, const vector<string>& candidate_keys)
{
    for(string valid_key : candidate_keys)
    {
        bool is_subset = true;
        for(char c : valid_key)
        {
            if(current_comb.find(c) == string::npos)
            {
                is_subset = false;
                break;
            }
        }
        if(is_subset) return false;
    }
    return true;
}

void dfs(int start, string current_comb, int m, vector<string>& combinations)
{
    if(!current_comb.empty())
    {
        combinations.push_back(current_comb);
    }
    for(int i = start; i < m; ++i)
    {
        current_comb += to_string(i);
        dfs(i + 1, current_comb, m, combinations);
        current_comb.pop_back();
    }
}

int solution(vector<vector<string>> relation) {
    int answer = 0;
    int n = relation.size();
    int m = relation[0].size();
    vector<string> combinations;
    vector<string> candidate_keys;
    dfs(0, "", m, combinations);
    
    sort(combinations.begin(), combinations.end(), [](const string& a, const string& b){
        return a.length() < b.length();
    });
    
    for(string comb : combinations)
    {
        if(!checkMinimality(comb, candidate_keys)) continue;
        
        set<string> unique_tuples;
        for(int i = 0; i < n; ++i)
        {
            string tuple_data = "";
            for(char c : comb)
            {
                int col_index = c - '0';
                tuple_data += relation[i][col_index] + ',';
            }
            unique_tuples.insert(tuple_data);
        }
        if(unique_tuples.size() == n)
            candidate_keys.push_back(comb);
    }
    
    return candidate_keys.size();
}

비트 마스킹 접근법:

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

bool checkMinimality(int current_mask, const vector<int>& candidate_keys)
{
    for(int valid_mask : candidate_keys)
    {
        if((current_mask & valid_mask) == valid_mask) 
            return false;
    }
    return true;
}

int solution(vector<vector<string>> relation) {
    int answer = 0;
    int n = relation.size();
    int m = relation[0].size();
    
    vector<int> combinations;
    vector<int> candidate_keys;
    
    for(int i = 1; i < (1 << m); ++i)
    {
        combinations.push_back(i);
    }
    
    sort(combinations.begin(), combinations.end(), [](const int& a, const int& b){
        return __builtin_popcount(a) < __builtin_popcount(b);
    });
    
    for(int mask : combinations)
    {
        if(!checkMinimality(mask, candidate_keys)) continue;
        set<string> unique_tuples;
        for (int i = 0; i < n; ++i) 
        {
            string tuple_data = "";
            for (int j = 0; j < m; ++j)
            {
                if(mask & (1 << j))
                   tuple_data += relation[i][j] + ",";
            }
            unique_tuples.insert(tuple_data);
        }

        if (unique_tuples.size() == n) 
        {
            candidate_keys.push_back(mask);
        }
    }
    

    
    
    return candidate_keys.size();
}

과제 진행하기[프로그래머스]

점찍기[프로그래머스]