[프로그래머스] 후보키

#include <bits/stdc++.h>
#define fastio cin.tie(0)->sync_with_stdio(0)
using namespace std;

vector<int> candidates; // 이미 검사한 후보키를 등록

bool isSubset(int target, int previous){
    return ((target & previous) == previous); // 포함되는지
}

bool check_minimality(int target){
    for(int previous : candidates){
        if(isSubset(target, previous))
            return false;
    }
    return true;
}



bool check_uniqueness(int i, vector<vector<string>> relation){
    int k = relation[0].size();
    vector<string> combined;
    
    for(auto v: relation){
        string temp ="";
        for (int j=0; j<k; j++)
            if((i&(1<<j)) !=0 )
                temp+=v[j];
        if(find(combined.begin(), combined.end(), temp) != combined.end())
            return false;
        else
            combined.push_back(temp);
    }
    return true;
}

int solution(vector<vector<string>> relation){
    int k=relation[0].size();
    for(int i=1; i<(1<<k); i++){
        if(check_uniqueness(i, relation) && check_minimality(i))
            candidates.push_back(i);
    }
    int answer = candidates.size();
    return answer;
}

<참고>

https://mingyum119.tistory.com/225

<풀이>

비트 마스크

비트마스크 i는 어떤 열들을 선택할지를 이진수로 표현한다.

k는 열의 개수이고 v = {"minji", "22", "seoul"}일 때 i=5이면 2진수로 101 이니까 temp 값이 "minjiseoul"이 되는 것이다

이렇게 유일성과 최소성을 맞춰서 조합을 찾는다. 

i & (1<<j): i의 j번째 비트를 검사하는것

1<<j: 1을 왼쪽으로 j칸 이동함

 

find는 찾으면 그 위치의 iterator를 반환하고 못 찾으면 end를 반환함

isSubset 함수

: 비트마스크로 표현된 두 집합 target과 previous가 있을 때, previous가 target의 부분집합인지 확인한다.

&연산을 통해 1인 비트만 남긴다.

예 1) target = 0111 (A, B, C), previous = 0011 (A, B)

→ 0111 & 0011 = 0011 

→ previous는 target의 부분집합이다

예 2) target = 0101 (A, C), previous = 0011 (A, B)

→ 0101 & 0011 = 0001 

→ B가 빠졌으므로 부분집합 아님