프로그래머스, 후보키, C++ [CPP] ★★★★★

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

나는.. 어려웠다.

그래서 다른 사람풀이를 보고 이해했다.

비트마스크를 써서 비교를 하는 것도 처음엔 생각하지 못했고

유일성이나 최소성에 관한 구현도 조금 힘들었다.

그래도 주석을 달면서 비트마스킹에 대한 감을 잡았다.

 

 

---

 

#맞은 풀이

#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <algorithm>
#include <set>

using namespace std;

// 최소성 확인
bool possi(vector<int> vec,int now){
    //지금까지 유일성이 확인된 vec 컨테이너의 원소들에 대해서
    //now가 최소성을 가지는지 확인
    for(int i = 0; i < vec.size(); i++)
        
        // ans에 있던 조합이 이번에 들어온 조합이랑 같은 것인지 확인
        // & 연산으로 now의 bits가 vec[i]를 포함한다는 것임(최소성 탈락)
        if((vec[i] & now) == vec[i])
            return false;

    return true;
}

int solution(vector<vector<string>> relation) {
    int rowSize = relation.size(); 
    int colSize = relation.front().size();
    vector<int> ans;

    //bit로 유일성확인
    //i => col 조사
    for(int i = 1; i < (1<<colSize); i++){
        set<string> s; // 최소성확인
        
        //해당 col에 대해서 행 간의 유일성(중복) 확인
        for(int j = 0; j < rowSize; j++){
            string now = "";
            for(int k = 0; k < colSize; k++){
                //선택된 col에 대해서 조사
                if(i & (1<<k))
                    now += relation[j][k];
            }
            s.insert(now);
        }
        
        //선택된 col에 대해서 중복체크 
        //s.size()가 조사한 rowSize와 같다면 중복된 것이 없다는 것
        //i bits에 대한 최소성 확인
        if(s.size() == rowSize && possi(ans,i))
            ans.push_back(i);
    }

    return ans.size();
}