[C++] 프로그래머스 - 후보키

2019 KAKAO BLIND RECRUITMENT (2019 카카오 블라인드 채용 문제)

릴레이션이 주어지고 후보키를 구하는 문제입니다.

후보키는 유일성과 최소성이 만족되어야합니다.
유일성은 아래의 학번과 같이 값들이 중복되지 않는 것을 의미합니다.
학번과 이름을 같이 사용하면 유일성은 만족하지만 최소성이 만족하지 않습니다.
후보키는 가장 작은 형태를 유지해야합니다.

ex)
학번 - O,
학번, 이름 - X,
학번, 전공 - X,
학번, 이름, 전공 - X
이름,전공 - O,
이름, 전공, 학년 - X
(전부 유일하지만 X인 것들은 최소성에 부합하지 않음)

 

먼저 유일성이 만족하는 조합들을 전부 찾은후에
최소성이 만족되지 않는 것들만 빼주어서 문제를 해결했습니다.

유일성이 만족하는 조합을 찾기위해 DFS를 사용하였습니다.

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
using namespace std;

vector<vector<string>> globalRelation;
vector<string> check;
int column;
int row;

bool compareAsc(string a, string b)
{
  return a > b;
}

bool compareCheck(string a, string b)
{
  return a.length() < b.length();
}

bool func(vector<string> v)
{
  sort(v.begin(), v.end(), compareAsc);
  for (int i = 0; i < column - 1; ++i)
  {
    if (v[i] == v[i + 1])
    {
      return false;
    }
  }
  return true;
}

void deduplication()
{
  for (int i = 0; i < check.size(); ++i)
  {
    string a = check[i];
    for (int j = 0; j < check.size(); ++j)
    {
      if (i == j)
      {
        continue;
      }

      string b = check[j];
      int aLen = check[i].length();
      int bLen = check[j].length();
      int count = 0;

      for (int k = 0; k < aLen; ++k)
      {
        for (int l = 0; l < bLen; ++l)
        {
          if (a[k] == b[l])
          {
            ++count;
          }
        }
      }
      if (count == aLen)
      {
        check.erase(check.begin() + j);
        --j;
      }
    }
  }
}

void DFS(string s, int n, vector<string> v)
{
  for (int i = 0; i < column; ++i)
  {
    v[i] += globalRelation[i][n];
  }

  if (func(v))
  {
    check.push_back(s);
  }

  for (int i = n + 1; i < row; ++i)
  {
    DFS(s + to_string(i), i, v);
  }
}

int solution(vector<vector<string>> relation)
{
  vector<string> v = {"", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", ""};
  globalRelation = relation;
  int answer = 0;

  column = relation.size();
  row = relation[0].size();

  for (int i = 0; i < row; ++i)
  {
    DFS(to_string(i), i, v);
  }

  sort(check.begin(), check.end(), compareCheck);

  deduplication();

  answer = check.size();

  return answer;
}