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

프로그래머스

입력받은 릴레이션에서 최소성을 만족하는 후보 키의 개수를 찾아주세요.

 

 

풀이 방법

후보키가 될 수 있는 속성의 모든 경우의 수를 찾아야합니다.

1개의 속성부터 ~ 8개의 속성이 하나의 후보키가 되는 것을 생각해볼 수 있겠습니다.

 

경우의 수가 너무 많을 것 같지만 순서에 상관없는 조합이기 때문에 100개 이하의 경우의 수가 나옵니다. 

// 속성 조합의 경우의 수를 찾는 함수
void FIND(vector<vector<int>>& result, int size, int max, int idx = 0, vector<int> v = vector<int>())
{
    if (v.size() == size)
    {
        result.push_back(v);
        return;
    }

    
    if (idx > max - (size - v.size()))
        return;
    
    for (int i = idx; i < max; i++)
    {
        v.push_back(i);
        FIND(answer, size, max, i+1, v);
        v.pop_back();
    }
}

...
...
...
for (int i = 1; i <= size; i++)
    {
        vector<vector<int>> a;
        FIND(a, i, size);

 

후보키 조합별로 중복되는 키가 있는지 체크하기 전

최소성을 만족하는지 체크 해야합니다.

ex) 속성번호(1, 2, 3)을 후보키로 체크할 때 (2, 3)만으로 후보키가 가능하다면 최소성을 만족하지 못하니 건너뜁니다.

저는 set을 이용하여 체크했습니다.

 

// 최소성 만족 여부를 체크하는 함수
bool CheckDuplicateKey(set<string>& keys, vector<int>& idxs)
{
    for (int i = 1; i <= idxs.size(); i++)
    {
        vector<vector<int>> a;
        FIND(a, i, idxs.size());
        
        for (auto& v : a)
        {
            string key = "";
            for (int& n : v)
                key += to_string(idxs[n]);
            
            if (keys.find(key) != keys.end())
                return true;
        }
    }
    
    return false;
}

 

해당 후보키가 최소성을 만족한다면 중복이 발생하는지 체크합니다.

for (int i = 0; i < relation.size(); i++)
{   
    string str = "";
    for (int& idx : v)
        str += relation[i][idx];

    if (s.find(str) == s.end())
        s.insert(str);
    else
    {
        //cout << "중복 발견\n";
        flag = false;
        break;
    }
}

 

중복이 발생하지 않는다면 후보 키의 개수를 + 1 해주며 반환해주어 마무리합니다.

 

 

정답 코드

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

void FIND(vector<vector<int>>& answer, int size, int max, int idx = 0, vector<int> v = vector<int>())
{
    if (v.size() == size)
    {
        answer.push_back(v);
        return;
    }

    if (idx > max - (size - v.size()))
        return;
    
    for (int i = idx; i < max; i++)
    {
        v.push_back(i);
        FIND(answer, size, max, i+1, v);
        v.pop_back();
    }
}

bool CheckDuplicateKey(set<string>& keys, vector<int>& idxs)
{
    for (int i = 1; i <= idxs.size(); i++)
    {
        vector<vector<int>> a;
        FIND(a, i, idxs.size());
        
        for (auto& v : a)
        {
            string key = "";
            for (int& n : v)
                key += to_string(idxs[n]);
            
            if (keys.find(key) != keys.end())
                return true;
        }
    }
    return false;
}


int solution(vector<vector<string>> relation) {
    int answer = 0;
    int size = relation[0].size();
    
    set<string> keys;
        
    for (int i = 1; i <= size; i++)
    {
        vector<vector<int>> a;
        FIND(a, i, size);
        
        int cnt = 1;
        for (auto& v : a)
        {
            if (CheckDuplicateKey(keys, v))
                continue;
            
            bool flag = true;             
            set<string> s;
            
            for (int i = 0; i < relation.size(); i++)
            {   
                string str = "";
                for (int& idx : v)
                    str += relation[i][idx];
                
                if (s.find(str) == s.end())
                    s.insert(str);
                else
                {
                    flag = false;
                    break;
                }
                
            }
            if (flag){
                string key = "";
                
                for (int& idx : v)
                    key += to_string(idx);
                    
                keys.insert(key);
                answer++;
            }
        }
    }
    return answer;
}