C++:: 프로그래머스 < 후보키 >

아래 코드와 비슷한 방식으로 접근하였으나 비트연산과 같이 간결한 코드를 발견하여 가져온 풀이이다. 기본적으로 해당 문제의 핵심적인 풀이는 속성들을 골랐을때 식별가능하면 정답을 1 올려주는 것인데, 이때 주의해야할 점이 해당 속성들이 식별가능한 최소단위여야 한다는 점이다.
간단한 예시로 속성1로 이미 식별이 가능하다면 속성1 + 속성2는 카운트해주면 안된다는 의미이다.(최소성 위배)
비트연산을 생각하지도 못했고 이와같은 방식으로 풀려면 상당한 연습이 필요하지 싶다...

#include <string>
#include <vector>
#include <set>
using namespace std;

// 조합 경우의 수
/*
     1(0001) - 학번
     2(0010) - 이름
     3(0011) - 이름, 학번
     4(0100) - 전공
     5(0101) - 학번, 전공
     6(0110) - 이름, 전공
     7(0111) - 학번, 이름, 전공
     8(1000) - 학년
     9(1001) - 학번, 학년
     10(1010) - 이름, 학년
     11(1011) - 학번, 이름, 학년
     12(1100) - 이름, 학번
     13(1101) - 학번, 전공, 학년
     14(1110) - 이름, 전공, 학년
     15(1111) - 학번, 이름, 전공, 학년
*/

bool possi(vector<int> vec, int now){
    for(auto v : vec)// &연산을 한결과가 0이 아니라는 뜻은 아무튼 뭔가는 포함되어있다는 의미
        if((v & now) == v)// 그 결과가 v와 같다는 것은 최소단위가 동일한지 체크하는 부분
            return false;
    return true;
}

int solution(vector<vector<string>> relation) {
    int rowSize = relation.size(); 
    int colSize = relation[0].size();
    int posible_cnt = 1 << colSize; 나올 수 있는 속성 조합
    vector<int> ans;

    for (int i = 1; i < posible_cnt; i++) {
        set<string> s;
        for (int j = 0; j < rowSize; j++) {
            string now = "";

            for (int k = 0; k < colSize; k++) {
                if (i & (1<<k)) now += relation[j][k];
            }
            s.insert(now);
        }
        if (s.size() == rowSize && possi(ans,i)) ans.push_back(i);
        // 사이즈가 같지않다면 중복된 값이 존재한다는 의미
        // Posii에서는 최소단위인지 측정
    }

    return ans.size();
}