[C++] 2019 KAKAO BLIND RECRUITMENT - 후보키

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

프로그래머스

 

 

 

 

 

 

#include <bits/stdc++.h>


int bitCount(int key) {
    int count = 0;
    while(key) {
        if (key & 1) ++count;
        key = key >> 1;
    }
    return count;
}

bool cmp(int key1, int key2) {
    return bitCount(key1) > bitCount(key2);
}


// 유일성 체크
bool unique_test(std::vector<std::vector<std::string>> relation, int row_size, int col_size, int candi) {
    for (int i = 0; i < row_size; ++i){
        for (int j = i + 1; j < row_size; ++j){
            
            bool is_same = true;
            for (int idx = 0; idx < col_size; ++idx) {
                if ((candi & 1 << idx) == 0) continue;
                if (relation[i][idx] != relation[j][idx]) {
                    is_same = false;
                    break;
                }
            }
            if (is_same) return false;
        }
    }
    return true;
}


int solution(std::vector<std::vector<std::string>> relation) {
    int answer = 0;
    int row_size = relation.size();
    int col_size = relation[0].size(); 
    
    std::vector<int> key_candi;
    
    for (int candi = 1; candi < 1 << col_size; ++candi) {
        if (unique_test(relation, row_size, col_size, candi)){
            key_candi.push_back(candi);
        }
    }
    
    
    // 최소성 체크
    std::sort(key_candi.begin(), key_candi.end(), cmp);
    
    while(!key_candi.empty()) {
        int key = key_candi.back(); key_candi.pop_back();
        ++answer;
        for (auto iter = key_candi.begin(); iter != key_candi.end(); ) {
            if ((key & *iter) == key) {
                iter = key_candi.erase(iter);
            }
            else {
                ++iter;
            }
        }
    }
    
    return answer;
}