후보키 풀이

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int bitnum(int i) {
	int counts = 0;
	while (i != 0) {
		if (i & 1)
			counts++;
		i = i >> 1;
	}
	return counts;
}

bool cmp(int a, int b) {
	if (bitnum(a) > bitnum(b))
		return true;
	return false;
}

bool uniquecheck(vector<vector<string>> v, int r, int c, int subset) {
	for (int i = 0; i < r-1; i++) {
		for (int j = i + 1; j < r; j++) {
			bool samecheck = true;
			for (int k = 0; k < c; k++) {
				if ( (1<<k & subset) == 0 )
					continue;
				if (v[i][k] != v[j][k]) {
					samecheck = false;
					break;
				}
			}
			if (samecheck)
				return false;
		}
	}
	return true;
}

int solution(vector<vector<string>> relation) {
	int answer = 0;
	int rowsize = relation.size();
	int colsize = relation[0].size();
	vector<int> unique;

	for (int i = 1; i < 1 << colsize; i++) {
		if (uniquecheck(relation, rowsize, colsize, i))
			unique.push_back(i);
	}

	sort(unique.begin(), unique.end(), cmp);

	while (!unique.empty()) {
		int n = unique.back();
		unique.pop_back();
		answer++;
		for (vector<int>::iterator it = unique.begin(); it != unique.end();) {
			if ((*it & n) == n)
				it = unique.erase(it);
			else
				it++;
		}
	}
	return answer;
}

https://www.youtube.com/watch?v=gCy00NeWag0의 동영상 풀이를 보고 풀었습니다!