문제
릴레이션을 나타내는 문자열 배열 relation이 매개변수로 주어질 때, 이 릴레이션에서 후보 키의 개수를 return 하도록 solution 함수를 완성하라. programmers
코드
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <set>
using namespace std;
int row;
int col;
int result = 0;
void get_keys(vector<vector<string>> &relation, vector<int> &ind, set<vector<int>> &is_used) {
// key: ind에서 1로 선택된 컬럼에 대한 값
// value: ind에서 0으로 선택된 컬럼에 대한 값
map<vector<string>, vector<string>> m;
bool is_okay = true;
for (int i = 0; i < row; i++) {
vector<string> cur_row = relation[i];
vector<string> key_of_m;
vector<string> value_of_m;
for (int j = 0; j < col; j++) {
if (ind[j] == 1) {
// key
key_of_m.push_back(cur_row[j]);
} else {
// value
value_of_m.push_back(cur_row[j]);
}
}
// find
if (m.count(key_of_m) == 1) {
// 이미 map 안에 존재하므로 value가 같은지 확인
vector<string> prev = m[key_of_m];
for (int j = 0; j < prev.size(); j++) {
if (prev[j] != value_of_m[j]) {
is_okay = false;
break;
}
}
if (!is_okay) break;
} else {
m[key_of_m] = value_of_m;
}
}
if (is_okay) {
vector<int> tmp;
for (int j = 0; j < ind.size(); j++) {
if (ind[j] == 1) {
tmp.push_back(j);
}
}
is_used.insert(tmp);
result++;
}
}
bool already_key(int num_of_one, vector<int> &ind, set<vector<int>> &is_used) {
// 현재 조합된 키보다 작은 수만큼만 확인(앞서 i가 증가만 하니까)
for (int i = num_of_one - 1; i > 0; i--) {
vector<int> v;
for (int j = 0; j < i; j++) v.push_back(1);
for (int j = 0; j < ind.size() - i; j++) v.push_back(0);
sort(v.begin(), v.end());
do {
vector<int> tmp;
for (int j = 0; j < ind.size(); j++) {
// 부분집합의 조합과 현재 조합이 현재 인덱스에서 1인지 확인
// 1의 개수만 작을뿐 부분집합이 아닐 수 있기 때문에
if (ind[j] == 1 && v[j] == 1) {
tmp.push_back(j);
}
}
// 이미 map에 존재
if (is_used.count(tmp) == 1) {
return true;
}
} while (next_permutation(v.begin(), v.end()));
}
return false;
}
int solution(vector<vector<string>> relation) {
row = relation.size();
col = relation[0].size();
set<vector<int>> is_used;
vector<int> ind;
// 총 컬럼수 중에 1개부터 총 컬럼수 범위의 i개 선택
for (int i = 1; i <= col; i++) {
// 조합
ind.clear();
for (int j = 0; j < i; j++) ind.push_back(1);
for (int j = 0; j < col - i; j++) ind.push_back(0);
sort(ind.begin(), ind.end());
do {
// 부분집합이 키로 사용되지 않았다면
if (!already_key(i, ind, is_used)) {
get_keys(relation, ind, is_used);
}
} while (next_permutation(ind.begin(), ind.end()));
}
return result;
}
풀이
1개부터 컬럼 수 만큼의 1과 0의 조합을 만든다. 1인 곳의 컬럼들이 최소성을 만족하는지 보기 위해 already_key 함수를 호출해서 확인한다. 예를 들면 already_key에서는 ind로 [1, 1, 0, 0]이 들어왔을 때 이미 [1, 0, 0, 0]이 후보키로 선택된 적이 있는지 확인한다. 각 키의 부분집합들이 후보키로 선택된 적이 없다면 ind가 1인 것을 key, 0인 것을 value로 하여 key-value 를 만족하는지를 get_keys에서 확인한다.