문제

릴레이션을 나타내는 문자열 배열 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에서 확인한다.