[프로그래머스] 2019 KAKAO BLIND RECRUITMENT - 후보키, C++

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

프로그래머스

본 문제는 후보 키를 찾는 문제로 후보 키가 될 수 있는 조합을 찾는 문제다. 조합을 구하는 문제는 비트 마스크를 이용하여 구할 수 있다. (비트 마스크는 디버깅하기 힘들지만 브루트 포스 문제에서 쉽게 순서를 정할 수 있다.) 가능한 모든 조합에서 최소성 검사, 유일성 검사 순으로 확인하면서 후보 키를 구하면 된다.

#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
 
using namespace std;
 
vector<int> ck;
 
bool is_minimality(int brute) {
    for (int i = 0; i < ck.size(); i++) {
        // (조건 2) 후보 키가 포함된 후보 키는 최소성을 만족하지 않는다.
        if ( (ck[i] & brute) == ck[i]) return false;
    }
    return true;
}
 
bool is_uniqueness(int brute, vector<vector<string>> relation) {
    
    vector<string> chk;
    for (int i = 0; i < relation.size(); i++) {
        string tmp = "";
        for (int j = 0; j < relation[i].size(); j++) {
            
            // 선택된 조합일 경우만 확인
            if ( (brute&(1 << j)) == 0) continue;
            tmp += relation[i][j];
        }
        chk.push_back(tmp);
    }
    
    // (조건 1) 후보 키는 유일하게 식별되어야 한다.
    // 중복을 제거하여 후보 키가 가능한지 확인한다.
    int before = chk.size();
    sort(chk.begin(), chk.end());
    chk.erase(unique(chk.begin(), chk.end()), chk.end());
    int after = chk.size();
    
    // 길이의 변화가 없다면 후보 키
    if (before - after == 0) return true;
    else return false;
}
 
int solution(vector<vector<string>> relation) {
    /*  다음과 같이 비트 마스크를 이용하여 조합을 구할 수 있다.
        1 - 0001 - {100}
        2 - 0010 - {ryan}
            ...
        15 - 1111 - {100, ryan music 2}
    */
    for (int brute = 1; brute < (1 << relation[0].size()); brute++) {
        
        // 최소성 검사
        if (!is_minimality(brute)) continue;
        // 유일성 검사
        if (!is_uniqueness(brute, relation)) continue;
        
        // 최소성과 유일성을 만족할 경우 후보 키로 저장
        ck.push_back(brute);
    }
    return ck.size();
}