1. 문제설명

관계 데이터베이스가 주어질 때 유일성, 최소성을 만족하는 집합의 개수를 구하라!
- 유일성(uniqueness) : 릴레이션에 있는 모든 튜플에 대해 유일하게 식별되어야 한다.
- 최소성(minimality)
  - 유일성을 가진 키를 구성하는 속성(Attribute) 중 하나라도 제외하는 경우 유일성이 깨지는 것을 의미한다.
  - 즉, 릴레이션의 모든 튜플을 유일하게 식별하는 데 꼭 필요한 속성들로만 구성되어야 한다.
문제 분류
- Combination, Backtracking, Simulation

2. 알고리즘 설계

모든 키 개수에 대한 조합 구하기
- 키 개수를 DFS 함수에 조건으로 걸어주었다.
- 키 개수를 만족하면 유일성, 최소성을 확인
  - 만족하면 현재 키의 구성을 후보키 목록에 기록한다.
  - 최소성 확인을 위해서!

유일성

unordered_map 구조를 사용하였다.
단순히 문자열로 col1col2와 같이 이어붙이고,
같은 게 있다면(현재 크기가 1보다 크다면) false 리턴

bool is_uniqueness() {
    unordered_map<string, int> tmp;  // (문자열, 개수)

    for (int i = 0; i < cpy.size(); i++) {
        string s = "";
        for (int j : keys) s += cpy[i][j];  // 데이터를 이어붙이고
        tmp[s]++;  // 문자열의 개수 1증가
        if (tmp[s] > 1) return false;  // 문자열의 개수가 2가 되면 중복
    }

    return true;
}

최소성

현재 입력된 키가 유일성을 만족하면서 하나의 키라면 최소성도 반드시 만족한다.
여러개라면 현재 저장된 후보키 목록과 비교할 필요가 있다.
- DFS를 통해 만들어진 키 조합을 unordered_map<int,int>로 카운팅
- 만약, 현재 키 조합이 전부 포함되는 후보키 리스트가 있다면 최소성을 만족하지 못한다.

bool is_minimality() {
    if (keys.size() == 1) return true;  // 유일성을 만족한 하나로 구성된 키 조합
  
    unordered_map<int, int> cmp;
    for (int k : keys) cmp[k]++;  // 키 조합 카운팅
  
    for (auto nxt : candidate) {  // 후보키 리스트를 하나씩 살피면서
        bool flag = false;
  
        // 현재 키 조합에서 하나라도 없는 게 있다면 넘어가고
        for (int x : nxt) {
            if (cmp[x] == 0) {
                flag = true;
                break;
            }
        }
		  
        // 후보키 리스트에 전부 포함된다면 불만족
        if (!flag) return false;
    }
  
    return true;
}

3. 전체 코드

#include <bits/stdc++.h>
using namespace std;

int ans, row, col;
vector<vector<string>> cpy;
bool vis[10];
vector<int> keys;
vector<vector<int>> candidate;

bool is_uniqueness() {
    unordered_map<string, int> tmp;

    for (int i = 0; i < cpy.size(); i++) {
        string s = "";
        for (int j : keys) s += cpy[i][j];
        tmp[s]++;
        if (tmp[s] > 1) return false;
    }

    return true;
}

bool is_minimality() {
    if (keys.size() == 1) return true;

    unordered_map<int, int> cmp;
    for (int k : keys) cmp[k]++;

    for (auto nxt : candidate) {
        bool flag = false;

        for (int x : nxt) {
            if (cmp[x] == 0) {
                flag = true;
                break;
            }
        }

        if (!flag) return false;
    }

    return true;
}

void DFS(int idx, int cnt, int total) {
    if (cnt == total) {
        if (is_uniqueness() && is_minimality()) {
            candidate.push_back(keys);
            ans++;
        }
        return;
    }

    for (int i = idx; i < col; i++) {
        if (vis[i]) continue;
        
        vis[i] = true;
        keys.push_back(i);
        DFS(i, cnt + 1, total);
        keys.pop_back();
        vis[i] = false;
    }
}

int solution(vector<vector<string>> relation) {
    cpy.assign(relation.begin(), relation.end());
    row = relation.size();
    col = relation[0].size();

    for (int i = 1; i <= col; i++)
        DFS(0, 0, i);

    return ans;
}

4. 소감

최소성에 대한 이해가 부족해 구글링을 통해 이론을 먼저 습득했다.
프로그래머스 문제 중에 이렇게 긴 코드는 오랜만에 작성해보았다.
프로그래머스 플랫폼 코딩 테스트의 경우, 거의 대부분 IDE를 쓰지 못한다.
- 그래서 코드가 짧은 문제들이 주로 나왔던 거 같다.

Programmers. 후보키

1. 문제설명

2. 알고리즘 설계

3. 전체 코드

4. 소감