[프로그래머스] 후보키

문제

lv2 후보키 문제 링크

학생들의 인적사항이 주어졌을 때, 후보 키의 최대 개수를 구하라

후보 키의 조건은 다음과 같다.
유일성(uniqueness) : 릴레이션에 있는 모든 튜플에 대해 유일하게 식별되어야 한다.
최소성(minimality) : 유일성을 가진 키를 구성하는 속성(Attribute) 중 하나라도 제외하는 경우 유일성이 깨지는 것을 의미한다. 즉, 릴레이션의 모든 튜플을 유일하게 식별하는 데 꼭 필요한 속성들로만 구성되어야 한다.

문제 풀이

먼저 후보 키의 조건을 이해해보자.
선택한 속성을 choice라는 문자열로 표현했다. ex) "023" = 학번, 전공, 학년, "0" = 학번
"0" 즉 학번을 선택하면 유일성을 만족한다. "1"은 apeach가 두 명이라서 유일성을 만족하지 않지만 "01"은 유일성을 만족한다. 하지만 "01"에서 "1"을 뺐을 때 "0"은 이미 유일성을 만족한다. 즉 "01"은 최소성을 만족하지 않는다.
"학번+이름"은 유일성은 만족하지만 "이름"을 빼고, "학번"만 사용해도 후보 키의 조건을 만족하기에 "학번+이름"은 최소가 아니라는 것이다.

후보 키를 이해했다면 풀이의 흐름은 다음과 같다.

1. 조합으로 선택할 수 있는 모든 경우(choice)를 구한다.
   "0", "1", "2", "3", "01", "02", "03", "12" ...
2. 각 choice에서 유일성을 만족하는지 판단한다.
3. 유일성을 만족한다면
   3-1. 유일성을 만족하는 choice를 담는 set에 담는다. (set의 이름은 uniq라고 하였고, 최소성 판단에 사용된다.)
   3-2. choice에서 속성을 하나씩 빼고, uniq에 있는지 확인한다. 예를 들어 choice: "123"이면 "23", "13", "12"가 uniq에 있는지(=유일성을 만족하는지)를 확인하는 것이다.
   하나라도 uniq에 있으면 최소성을 만족하지 않는 것이고, "23", "13", "12" 모두 uniq에 없다면 "123"은 유일성, 최소성을 둘 다 만족하는 후보 키가 된다.

소스코드

#include <string>
#include <vector>
#include <set>

using namespace std;

int answer = 0;
int relationCnt;
int tupleCnt;
vector<vector<string>> rel;
vector<bool> visit;
set<string> uniq; // 유일성을 만족하는 choice들

bool check(string choice) {
    set<string> countUniq;
    // choice에 선택된 속성을 더하여 유일성 체크 ex) 첫 번째 튜플에서 choice: "01"이라면 tmp: "100ryan"
    for (int i = 0; i < tupleCnt; i++) {
        string tmp = "";
        for (int j = 0; j < choice.size(); j++) {
            int idx = choice[j] - '0';
            tmp += relCopy[i][idx];
        }
        countUniq.insert(tmp);
    }
    if (countUniq.size() == tupleCnt) { // 유일성 만족
        uniq.insert(choice);
        if (choice.size() == 1) return true;
        for (int i = 0; i < choice.size(); i++) {
            string tmpChoice = choice;
            tmpChoice.erase(tmpChoice.begin() + i);
            if (uniq.count(tmpChoice) == 1) return false; // 최소성 만족 X
        }
        return true; // 최소성 만족
    }
    return false;
}

void comb(int cnt, int idx, int n) {
    if (cnt == n) {
        string choice = ""; // 선택된 인덱스 나열
        for (int i = 0; i < visit.size(); i++) {
            if (visit[i]) choice += to_string(i);
        }
        if (check(choice)) { // 유일성 최소성을 모두 만족하면
            answer++;
            return;
        }
        return;
    }
    for (int i = idx; i < relationCnt; i++) {
        if (visit[i]) continue;
        visit[i] = true;
        comb(cnt + 1, i + 1, n);
        visit[i] = false;
    }
}

int solution(vector<vector<string>> relation) {
    relationCnt = relation[0].size();
    tupleCnt = relation.size();
    visit.assign(relationCnt, false);
    rel = relation;
    for (int i = 1; i <= relationCnt; i++) {
        comb(0, 0, i);
    }
    return answer;
}