2019 Kakao blind 42890 - 후보키(완전탐색, 비트마스킹) c++ 풀이

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

코딩테스트 연습 - 후보키

- 일단 후보키 개념이 문제에서 설명되어 있지만 이 개념을 미리 알고 있어야 더 쉽게 접근해볼만한 문제였다. 후보키 개념이 잘 이해가 안 가서 데이터베이스 대학강의를 다시 들어보았다. 알고리즘 과목 외의 CS개념이 있어야 이해가 가능한 문제라서 레벨2는 아니고 3정도는 줘야되는 문제 같다.

- 어떤 단일 속성이 유일성을 만족한다면 후보키가 된다. 그리고 어떤 속성의 조합이 유일성을 만족하면서 하나라도 빠졌을 때 유일성을 만족하지 않는 경우가 없다면 최소성도 만족하여 후보키가 될 수 있다.

따라서 릴레이션 속성의 가능한 모든 조합을 만들어서 이 조합이 유일성과 최소성을 만족해서 후보키가 될 수 있는지 체크하는 방식으로 풀 수 있다. 

먼저 모든 조합에 대해서 유일성 검사를 해서 통과한 조건만 최소성 검사를 하는 식으로 문제를 풀었는데 비트마스킹으로 유일성을 만족하는 최소갯수의 특정조합을 해당 조합이 가지고 있는지 검사하는 방식으로 접근하였다. 

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

bool isUniq(vector<vector<string>>& relation, int r, int c, int bit) {
    for (int i = 0; i < r - 1; ++i) {  // 모든 튜플에 대해 유일하게 식별
        for (int j = i + 1; j < r; ++j) {
            bool isSame = true;
            for (int k = 0; k < c; ++k) {
                if ((bit & 1 << k) == 0) continue;  // 1, 10, 100, 1000
                if (relation[i][k] != relation[j][k]) {
                    isSame = false;
                    break;
                }
            }

            if (isSame) return false;
        }
    }

    return true;
}

int countBit(int bit) {
    int cnt = 0;
    while (bit) {
        if (bit & 1) ++cnt;
        bit = bit >> 1;
    }

    return cnt;
}

// 모든 필드의 멱집합 만들고, 유일성, 최소성 체크
int solution(vector<vector<string>> relation) {
    int ans = 0;
    int r = relation.size();
    int c = relation[0].size();

    vector<int> candidate;
    for (int i = 1; i < 1 << c; ++i) {                          // 0001~1111
        if (isUniq(relation, r, c, i)) candidate.push_back(i);  // 유일성 만족
    }

    sort(candidate.begin(), candidate.end(), [](int bit1, int bit2) {
        return countBit(bit1) > countBit(bit2);
    });

    while (!candidate.empty()) {
        int n = candidate.back();  // 최소성 만족
        candidate.pop_back();
        ++ans;

        for (auto it = candidate.begin(); it != candidate.end();) {
            if ((n & *it) == n)
                it = candidate.erase(it);
            else
                ++it;
        }
    }

    return ans;
}