[프로그래머스] 후보키

링크

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

프로그래머스

풀이

후보 키의 최대 개수를 구하는 문제인데.

 

모든 키의 조합을 확인 해봐야 하기 때문에 비트마스킹을 이용하여 풀었습니다.

 

1. 비트마스킹을 이용하여 키의 모든 조합을 구하고

2. 구해진 키의 모든 조합이 유일성을 만족하는지 확인

3. 최소성을 확인하기 위해 키의 사용이 작은 순서대로 키의 사용이 많은것을 비교하여 최소성을 만족하지 않는 키의 조합을 없애준다.

 

#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#include<string>
#include<set>
#include<map>
#include<cstring>
#include<functional>
#include<cmath>
#include<stack>

#define SIZE 1010
const int INF = 2000000000;

using namespace std;

typedef long long int ll;

set<vector<int>> key;

map<int, vector<int>> check;
int solution(vector<vector<string>> relation) {
	int c_size = relation[0].size();
	int r_size = relation.size();

	//비트 마스크로 모든 조합 구하기
	for (int i = 1; i < (1<<c_size); i++) {
		vector<int> index;
		for (int j = 0; (1<<j) <= i; j++) {
			if ((i & (1<<j)) == (1<<j))
				index.push_back(j);
		}

		//구해진 조합을 이용하여 유일성을 만족하는지 확인
		set<vector<string>> tmp_key;
		for (int k = 0; k < r_size; k++) {
			vector<string> s;
			for (int j = 0; j < index.size(); j++) {
				s.push_back(relation[k][index[j]]);
			}
			tmp_key.insert(s);
		}

		//유일성을 만족하면 조합을 추가
		if (tmp_key.size() == r_size) {
			check[index.size()].push_back(i);
		}
	}

	int cnt = 0;
	//최소성을 확인 하기 위해 키의 갯수를 적은 것부터 탐색
	for (int i = 1; i <= r_size; i++) {
		for (auto c : check[i]) {
			if (c == 0)
				continue;

			cnt++;

			for (int j = i + 1; j <= r_size; j++) {
				for (int jj = 0; jj < check[j].size(); jj++) {
					if ((c&check[j][jj]) == c) {
						check[j][jj] = 0;
					}
				}
			}
		}
	}
	
	return cnt;
}