[프로그래머스 2] 후보키 (C/C++) (★★★)

1.

#include <string>
#include <vector>
#include <iostream>
#include <map>
using namespace std;
 
vector<vector<string>> relations;
vector<int> ans;
int row;
int col;
 
int check_min(int bit)
{
    // 모든 튜플을 유일하게 식별하는 데 꼭 필요한 속성들로만 구성되어있지 않다면, 최소성 만족 X
    for(int i = 0; i < ans.size(); i++)
    {
        if((ans[i] & bit) == ans[i])
        {
            return 0;
        }
    }
 
    // 최소성 만족 O
    return 1;
}
 
int solution(vector<vector<string>> relation) 
{
    relations = relation;
    row = relation.size();
    col = relation[0].size();
    
    // 릴레이션에 있는 모든 튜플에 대해 유일하게 식별되어야 한다 -> 유일성 만족 O
    for(int i = 1; i < (1 << col); i++)
    {
        map<string, int> check;
        
        for(int j = 0; j < row; j++)
        {
            string now;
            
            for(int k = 0; k < col; k++)
            {
                if(i & (1 << k))
                {
                    now += relation[j][k];        
                }
            }
            
            check[now] = 1;
        }
        
        if(check.size() == row && check_min(i) == 1)
        {
            ans.push_back(i);
        }
    }
    
    return ans.size();
}
 

 

2.

#include <string>
#include <vector>
#include <iostream>
#include <map>
using namespace std;
 
vector<vector<string>> relations;
vector<int> ans;
int row;
int col;
 
int check_min(int bit)
{
    // 모든 튜플을 유일하게 식별하는 데 꼭 필요한 속성들로만 구성되어있지 않다면, 최소성 만족 X
    for(int i = 0; i < ans.size(); i++)
    {
        if((ans[i] & bit) == ans[i])
        {
            return 0;
        }
    }
 
    // 최소성 만족 O
    return 1;
}
 
int solution(vector<vector<string>> relation) 
{
    relations = relation;
    row = relation.size();
    col = relation[0].size();
    
    // 릴레이션에 있는 모든 튜플에 대해 유일하게 식별되어야 한다 -> 유일성 만족 O
    for(int i = 1; i < (1 << col); i++)
    {
        map<string, int> check;
        
        for(int j = 0; j < row; j++)
        {
            string now;
            
            for(int k = 0; k < col; k++)
            {
                if(i & (1 << k))
                {
                    now += relation[j][k];        
                }
            }
            
            check[now] = 1;
        }
        
        if(check.size() == row && check_min(i) == 1)
        {
            ans.push_back(i);
        }
    }
    
    return ans.size();
}