Programmers : 후보키

문제링크

풀이요약

비트마스킹 (답안참조)

풀이상세

1. 비트마스킹을 통해, 현재 나올 수 있는 모든 부분집합을 구한다.

2. 임의의 부분집합에 해당하는 문자열을 set 에 포함시킨다. 만약 포함시키기 전 set 의 길이와 포함시킨 후 set 의 길이가 동일하다면 이는 유일성을 만족하지 못하며, 후보키가 될 수 없게 된다.

3. 모든 탐색 후에, set 의 길이와 로우의 길이가 동일하다면 그건 후보키가 될 수 있다. 현재의 비트마스킹을 값을 vector 에 넣어준다.

4. 만약 임의의 비트마스킹 값이 vector 에 존재하는 경우, 이미 후보키에 반영되어 있기에 최소성을 만족하지 못하므로 이 경우도 제외하여 탐색한다.

배운점

• 비트마스킹 문제를 여러번 풀어봐야겠다.

#include <unordered_set>
#include <string>
#include <vector>
using namespace std;
vector<int> v;
unordered_set<string> ss;

bool check(int idx) {
    for(auto i : v) {
        if((i&idx)==i) return false;
    }
    return true;
}

int solution(vector<vector<string>> relation) {
    int answer = 0;
    for(int i=1; i< (1 << relation[0].size()); i++) {
        if(!check(i)) continue;
        ss.clear();
        for(int j=0; j<relation.size(); j++) {
            string curr = "";
            for(int k=0; k<relation[0].size(); k++) {
                if(((1 << k) & i) > 0) curr += relation[j][k];
            }
            int prev_len = ss.size();
            ss.insert(curr);
            if(prev_len==ss.size()) break;
        }
        if(ss.size() == relation.size()) v.push_back(i);
    }

    return v.size();
}