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

후보키(Level 2)

문제

전체 문제 보기

코딩테스트 연습 - 후보키

접근법

이번 문제는 하나 이상의 속성을 선택하여 만들 수 있는 후보키의 개수를 구하는 문제입니다. 하나 이상의 속성을 선택하기 위해서는 백트레킹을 활용하여 재귀적으로 접근할 수 있습니다. 재귀적으로 선택된 속성의 조합이 문제에서 주어진 "유일성"과 "최소성"을 만족하는지 검증하여 후보키로 확정 지을 수 있습니다. 이렇게 정해진 후보키의 개수를 출력하면 문제에서 요구하는 정답을 구할 수 있습니다.

구현

탐색 순서

우선 아래와 같이 후보키의 개수를 1개부터 속성의 개수까지 탐색을 합니다. 0,1,2번 속성이 있을 때 이들을 뽑을 수 있는 모든 경우의 수를 오름차순으로 정리하면 다음과 같을 것입니다.

0
0 1
0 2
0 1 2
1
1 2
2

그런데 만약 2가 후보키라면, "0 2", "0 1 2", "1 2"에서 "유일성"을 만족하게 됩니다. 그런데 2가 탐색되기 전에 이들이 먼저 탐색되어서 "최소성"을 만족하지 못하는 키들이 후보키로 등록되는 문제가 발생할 수 있습니다. 따라서 다음처럼 속성의 개수가 1개인 것부터 N개까지 탐색할 필요가 있습니다.

0
1
2
0 1
0 2
1 2
0 1 2

위와 같은 순서로 탐색을 진행하기 위해서 다음과 같이 목표 깊이를 지정해줄 수 있습니다.

void BT(vector<vector<string>>& relation, 
        vector<int>& candidate, 
        set<vector<int>>& candidateKeys, 
        int idx, 
        int targetDep)
{  
    if(targetDep == candidate.size())  
    {
        // 후보키 발견
        if(IsValid(relation, candidate, candidateKeys))
        {
            candidateKeys.insert(candidate);
            return;
        }
    }

    const int colSize = relation[0].size();
    for(int i = idx; i < colSize; ++i)
    {
        candidate.push_back(i);
        // 탐색하려는 후보키가 완성된 후보키에 없다면 탐색 진행
        if(candidateKeys.find(candidate) == candidateKeys.end())
            BT(relation, candidate, candidateKeys, i + 1, targetDep);
        candidate.pop_back();
    }

    return;
}
int solution(vector<vector<string>> relation) {
    int answer = 0;
    vector<int> candidate;
    set<vector<int>> candidateKeys;
    const int colSize = relation[0].size();
    for(int i = 1; i <= colSize; ++i)
    {
       BT(relation, candidate, candidateKeys, 0, i);
    }
    answer = candidateKeys.size();
    return answer;
}

후보키 유효성 검증

후보키는 "유일성"과 "최소성"을 만족해야 합니다. 선택한 속성들의 조합이 "유일성"과 "최소성"을 만족하는지 다음과 같이 확인할 수 있습니다.

• 유일성: 현재 선택한 속성들로 튜플을 구성하였을 때 중복된 값이 없는지 확인합니다. 
• 최소성: 현재 선택한 속성들의 서브셋이 등록된 이미 등록된 후보키와 중복되는지 확인합니다. 만약 중복되는 후보키가 존재한다면 현재 속성들을 더 작은 단위로 나눌 수 있기 때문에 "최소성"을 만족하지 않음을 알 수 있습니다.

bool IsMinimality(const vector<int>& candidate, 
                const set<vector<int>>& candidateKeys, 
                vector<int>& temp, 
                int idx)
{

    if(candidateKeys.find(temp) != candidateKeys.end())
    {
        return false;
    }

    int size = candidate.size();
    for(int i = idx; i < size; ++i)
    {
        temp.push_back(candidate[i]);
        if(IsMinimality(candidate, candidateKeys, temp, i + 1) == false)
            return false;       
        temp.pop_back();
    }
    return true;

}
bool IsValid(const vector<vector<string>>& relation, 
            const vector<int>& candidate, 
            const set<vector<int>>& candidateKeys)
{
    // 유일성 검증
    set<string> keys;
    for(const auto& row : relation )
    {
        string str;
        for(int col : candidate)
        {
            str += row[col];
        }
        auto result = keys.insert(str);

        // 중복된 키가 존재할 경우 유효하지 않은 후보키이다.
        if(result.second == false)
            return false;
    }
    // 최소성 검증
    vector<int> temp;
    if(IsMinimality(candidate, candidateKeys, temp, 0) == false)
    {
        return false;
    }
    // 유일성과 최소성을 만족한 경우
    return true;
}

전체 소스 코드

전체 소스 코드는 다음과 같습니다.

#include <string>
#include <vector>
#include <set>
#include <iostream>
using namespace std;
bool IsMinimality(const vector<int>& candidate, 
                const set<vector<int>>& candidateKeys, 
                vector<int>& temp, 
                int idx)
{

    if(candidateKeys.find(temp) != candidateKeys.end())
    {
        return false;
    }

    int size = candidate.size();
    for(int i = idx; i < size; ++i)
    {
        temp.push_back(candidate[i]);
        if(IsMinimality(candidate, candidateKeys, temp, i + 1) == false)
            return false;       
        temp.pop_back();
    }
    return true;

}
bool IsValid(const vector<vector<string>>& relation, 
            const vector<int>& candidate, 
            const set<vector<int>>& candidateKeys)
{
    // 유일성 검증
    set<string> keys;
    for(const auto& row : relation )
    {
        string str;
        for(int col : candidate)
        {
            str += row[col];
        }
        auto result = keys.insert(str);

        // 중복된 키가 존재할 경우 유효하지 않은 후보키이다.
        if(result.second == false)
            return false;
    }
    // 최소성 검증
    vector<int> temp;
    if(IsMinimality(candidate, candidateKeys, temp, 0) == false)
    {
        return false;
    }
    // 유일성과 최소성을 만족한 경우
    return true;
}

void BT(vector<vector<string>>& relation, 
        vector<int>& candidate, 
        set<vector<int>>& candidateKeys, 
        int idx, 
        int targetDep)
{  
    if(targetDep == candidate.size())  
    {
        // 후보키 발견
        if(IsValid(relation, candidate, candidateKeys))
        {
            candidateKeys.insert(candidate);
            return;
        }
    }

    const int colSize = relation[0].size();
    for(int i = idx; i < colSize; ++i)
    {
        candidate.push_back(i);
        // 탐색하려는 후보키가 완성된 후보키에 없다면 탐색 진행
        if(candidateKeys.find(candidate) == candidateKeys.end())
            BT(relation, candidate, candidateKeys, i + 1, targetDep);
        candidate.pop_back();
    }

    return;
}

int solution(vector<vector<string>> relation) {
    int answer = 0;
    vector<int> candidate;
    set<vector<int>> candidateKeys;
    const int colSize = relation[0].size();
    for(int i = 1; i <= colSize; ++i)
    {
       BT(relation, candidate, candidateKeys, 0, i);
    }
    answer = candidateKeys.size();
    return answer;
}