[Programmers] 후보키

#include<iostream>
#include<vector>
#include<map>
#include<set>
using namespace std;

bool chk(vector<int> v, int value){
    int size = (int) v.size();
    /*
     후보키라 생각되는 value값과
     기존에 후보키를 저장하고 있는 vector 값들에 대해
     & 연산을 통해 value값이 후보키가 될 수 있는지 판별한다.
     
     만약
     001이라는 값이 vector에 있다면
     그 뜻은 1번째 컬럼이 후보키라는 뜻이다.
     
     여기서 value가 101이라는 값이라면
     그 뜻은 1,3번째로 예비 후보키를 만들었고
     101
     & 001을 하게 되면
     중복되는 값이 있기 때문에 절대 0이 나올 수 없게 된다.
     
     즉 1번째 컬럼만으로 유일성과 최소성을 만족하기에
     1,3번째로 만든 후보키(=value)는
     유일성은 만족하되
     최소성을 만족하지 못하기 때문에 후보키가 될 수 없다.
     */
    for(int i=0; i<size; i++){
        if((v[i] & value) == v[i])
            return false;
    }
    return true;
}

int solution(vector<vector<string>> r){
    int ans = 0;
    int row = (int)r.size(); // n is row
    int column = (int)r[0].size(); // m is column
    
    vector<int> v;
    /*
     i 변수는 조합할 수 있는 총 경우의 수를 뜻한다.
     m이 3이라면
     가능한 조합의 수는 2^3 = 8개이다.
     이 값을 비트로 표현하자면
     1 << m = 1 << 3 = 8이 된다.
     즉 모든 경우의 수를 다 탐색하는 경우의 수이다.
     또한
     001 -> 010 -> 011 -> 100 -> 101 -> 110 -> 111 순서로 진행을 하는데
     이 값들은 각각
     1번째 컬럼으로 체크
     2번째 컬럼으로 체크
     1,2번째 컬럼으로 체크
     3번째 컬럼으로 체크
     1,3번째 컬럼으로 체크
     2,3번째 컬럼으로 체크
     1,2,3번째 컬럼으로 체크를 한다.
     */
    for(int i=1; i<(1<<column); i++){
        map<string, int> m;
        set<string> se;
        for(int j=0; j<row; j++){
            string s = "";
            /*
             k 변수는 각 컬럼을 가리킨다.
             그렇다면 어떻게 활용하느냐?
             k값에 따라
             (1<<k) 부분은
             k = 0 --> 001
             k = 1 --> 010
             k = 2 --> 100처럼 표현이 된다.
             다시 말해
             비트 자리수가 몇 번째 컬럼인지를 뜻하게 된다.
             
             이 부분을 i와 연결시켜 생각해본다면
             i가 101이라면
             그 뜻은 1,3번째 컬럼으로 후보키를 만들 수 있는지를 판단하는 상황이다.
             이 때
             k=0,2일 때
             각각 값은 001과 100이 된다.
             또한 각각 if 조건이 True가 되기 때문에
             s 변수에 해당 컬럼값을 (+) 해주게 되면
             그 값으로 후보키 자격을 갖출 수 있는지 체크할 수 있게 된다.
             더 자세히 말하면
             일단 1,3번째 값을 합친다음에
             map or set 컨테이너에 넣는다.
             만약 중복되는값이 있다면
             map or set 컨테이너의 size는 n보다 작을 것이다.
             */
            for(int k=0; k<column; k++){
                if( i & (1<<k) )
                    s += r[j][k];
            } // end of for k
            m[s]++;
//            se.insert(s); // set을 사용한다면
        } // end of for j
        
        /*
         우선은 map or set 컨테이너의 사이즈가 n개 일 때
         중복되는 값이 없다는 뜻이다.
         그리고 현재 만들어진 후보키가
         기존의 후보키인 값 + @ 로 만들어져있는지 체크하기 위한 작업을 실시한다.
         Why?
         기존의 후보키 값 + @는 유일성은 만족하지만 최소성은 만족하지 못하기 때문이다.
         */
        if( m.size() == row && chk(v,i) ){
//        if( se.size() == row && chk(v,i) ) // set을 사용한다면
            /*
             모든 조건을 충족시켰을 시
             i값을 저장시킨다.
             다시 한번 짚고 넘어가자면
             만약 i가 5(=101)일 경우는
             1,3번째 컬럼으로 후보키를 만들었을 경우를 뜻한다.
             */
            v.push_back(i);
        }
    } // end of for i
    
    ans = (int)v.size();
    return ans;
}

int main(){
    
    vector< vector<string> > relation = {
        {"100","ryan","music","2"},
        {"200","apeach","math","2"},
        {"300","tube","computer","3"},
        {"400","con","computer","4"},
        {"500","muzi","music","3"},
        {"600","apeach","music","2"}
    };
    
    int ans = solution(relation);
    
    cout << ans << endl;
    return 0;
}