[프로그래머스]2019 KAKAO BLIND RECRUITMENT : 후보키 (level 2)(c++)

https://programmers.co.kr/learn/courses/30/lessons/42890

코딩테스트 연습 - 후보키

 

비트마스크 활용

#include <string>
#include <vector>
#include <unordered_set>

using namespace std;

bool check_minimality(const vector<int> &keys, const int bit)
{
    // 현재 속성 집합이 기존의 후보키를 포함하면 false반환
    for (int i = 0; i < keys.size(); ++i)
    {
        if ((keys[i] & bit) == keys[i])
        {
            return false;
        }
    }
    return true;
}

int solution(vector<vector<string>> relation) {

    vector<int> keys;
    int cnt = 0;
    int tpl_len = relation.size();
    int clmn_len = relation[0].size();

    // 후보키 속성 구성을 비트마스크 순열로 조합하기
    for (int bit = 1; bit < (1 << clmn_len); ++bit)
    {
        // 최소성 만족 여부 검사
        if (!check_minimality(keys, bit))
        {
            continue;
        }

        // 유일성 만족 여부 검사
        unordered_set<string> set;
        for (int i = 0; i < tpl_len; ++i)
        {
            string key;
            for (int j = 0; j < clmn_len; ++j)
            {
                // 현재 속성 집합에 해당하는 value를 이어붙여서 set에 push하기
                if (bit & (1 << j))
                {
                    key += relation[i][j] + ' ';    // 속성간 구분자 추가
                }
            }
            set.insert(key);
        }

        // 중복되는 튜플이 없으면 후보키 벡터에 push, 카운팅
        if (set.size() == tpl_len)
        {
            keys.push_back(bit);
            ++cnt;
        }
    }
    
    return cnt;
}

 

얼마전에 BOJ에서 비트마스크 문제를 좀 풀었더니 괜찮게 풀렸다.

특히 최소성 만족 여부를 검사할때 비트 연산이 아주 유용했다.

 

 

TIP1

집합의 포함여부를 검사하기.

// bit가 keys[i]를 완전히 포함하는지 검사
if ((keys[i] & bit) == keys[i])

 

 

TIP2

string에 속성값 이어붙일 때 구분자 넣어주기

if (bit & (1 << j))
{
    key += relation[i][j] + ' ';    // 속성간 구분자 추가
}

구분자를 넣지 않으면 ["ab","c"] 튜플과 ["a", "bc"] 튜플이 같게 인식된다.

현재는 프로그래머스에서 구분자에 대한 테스트케이스가 없는데, 나중에 추가 될 듯하다.